rulinux.net - Форум - Talks - а как скорость алгоритмов рассчитывается?

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

Mon, 22 Nov 2010 16:42:02 +0300

>вот например пишут этот алгоритм имеет скорость 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.

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

Sun, 21 Nov 2010 14:26:44 +0300

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

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

Sat, 20 Nov 2010 22:09:53 +0300

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

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

Sat, 20 Nov 2010 17:31:54 +0300

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

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

Sat, 20 Nov 2010 12:53:44 +0300

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

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

Sat, 20 Nov 2010 12:31:00 +0300

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

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