anonymous@RULINUX.NET~# Last login: 2024-12-23 20:02:35
Регистрация Вход Новости | Разметка | Пользователи | Галерея | Форум | Статьи | Неподтвержденное | Трекер | Правила форума | F.A.Q. | Ссылки | Поиск
[#] [Добавить метку] [Редактировать]
Скрыть

а как скорость алгоритмов рассчитывается?

вот например пишут этот алгоритм имеет скорость O(log n), где n - что такое? или O(n^2)

Число итераций в цикле или например число атомарных элементов данных с которыми производятся действия?

vilfred(*) (2010-11-20 16:31:00)

Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.2.12) Gecko/20101026 AdCentriaIM/1.7 Firefox/3.6.12

[Ответить на это сообщение]
avatar
Скрыть

Re: а как скорость алгоритмов рассчитывается?

Вроде как количество операций. Например, 2*3*5=30 => 3 операции.

svarwik(*)(2010-11-20 16:53:44)

Mozilla/5.0 (X11; U; Linux i686; en-US) AppleWebKit/533.3 (KHTML, like Gecko) rekonq Safari/533.3
avatar
Скрыть

Re: а как скорость алгоритмов рассчитывается?

я это вообще не понимаю. есть матан, в нем есть о малое и О большое, они разные в случае разных ситуаций. видимо не просто так народ те же самые параллели проводит и со скоростью вычисления алгоритмов. вот.

vilfred(*)(2010-11-20 21:31:54)

Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.2.12) Gecko/20101026 AdCentriaIM/1.7 Firefox/3.6.12
avatar
Скрыть

Re: а как скорость алгоритмов рассчитывается?

Это оценка скорости роста трудоёмкости алгоритма в зависимости от роста входных данных (n).

anonymous(*)(2010-11-21 02:09:53)

Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.12) Gecko/20101108 Gentoo Firefox/3.6.12
avatar
Скрыть

Re: а как скорость алгоритмов рассчитывается?

а что такое трудоемкость алгоритма? мож где ссылка есть прочитать?

vilfred(*)(2010-11-21 18:26:44)

Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.2.12) Gecko/20101026 AdCentriaIM/1.7 Firefox/3.6.12
avatar
Скрыть

Re: а как скорость алгоритмов рассчитывается?

>вот например пишут этот алгоритм имеет скорость O(log n), где n - что такое? или O(n^2)
>Число итераций в цикле или например число атомарных элементов данных с которыми производятся действия?
При помощи n обозначают величину проблемы. А величина проблемы является частью описания проблемы (это которое "Дано"), также как и атомарные операторы. Практичиски же, величина дефининируется таким образом чтобы максимально хорошо характеризовать величину проблемы. Вот тебе примеры:

1) Найти решение системы уровнених Ах=b, где b вектор m x 1, А матрица m x m. Здесь имет смысл дефининировать n = m. Атомарные операторы: умножение и сложение.

2) Найти произведение двух (m=2) больших чисел из p бит (например 4098 ) . Здесь имеет смысл дефинировать n = p. Операторы: умножение и деление с 32-битными регистрами. (Сравни с (1) где умножение атомарно).

3) Решить TSP (Travelling Salesman Problem). Где количество городов равняется q. Некоторые алгоритмы будут переодически искать решение уравнения Ах=b , b вектор mx1. Но по сравнению с другими операциями затрачиваемое на это время настолько мало, что можно дефинировать это умножение как атомарную операцию. В TSP величина проблемы n=q.

anonymous(*)(2010-11-22 20:42:02)

Mozilla/5.0 (X11; U; Linux i686; de; rv:1.9.2.12) Gecko/20101027 Ubuntu/10.04 Firefox/3.6.12
Этот тред читают 1 пользователь:
Анонимных: 1
Зарегистрированных: 0




(c) 2010-2020 LOR-NG Developers Group
Powered by TimeMachine

Valid HTML 4.01 Transitional Правильный CSS!