Невозможно вывести таблицу об эффективности алгоритмов - PullRequest
Новая
       13

Невозможно вывести таблицу об эффективности алгоритмов

0 голосов
/ 28 июня 2009

Я не совсем уверен насчет следующей таблицы

альтернативный текст http://files.getdropbox.com/u/175564/algTranslation.png

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

Меня интересует вывод таблицы.

Таблица подсказывает мне, что

  • O (n) = 10M в секунду (Это похоже на мощность современных компьютеров)
  • n - количество обрабатываемых элементов # Спасибо Гуффе!

Я не уверен, как были получены значения в столбце O (n * log (n)).

  1. Как вы можете вывести значение 0,5M для O (n * log (n)) или 3000 для O (n ^ 2)?

Ответы [ 3 ]

4 голосов
/ 28 июня 2009

Нет, n - это не количество секунд, это количество элементов для обработки.

O (n) означает, что время обработки элементов линейно по отношению к количеству элементов.

O (n²) означает, что время для обработки предметов относительно квадрата количества предметов. Если вы удвоите количество предметов, время обработки увеличится в четыре раза.

См .: Big O нотация

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

Edit:
Значения вдоль оси x таблицы являются лишь приблизительными значениями, основанными на предположении, что работа на элемент одинакова. Например, значение 3000 для O (n²) округлено от квадратного корня из 10 миллионов, что составляет ~ 3162.28. Кубический корень из 10 миллионов - это не 200, а ~ 215,44.

В реальной ситуации два алгоритма редко выполняют одинаковый объем работы на элемент. Алгоритм с O (log n) обычно выполняет больше работы на элемент, чем алгоритм O (n) для той же цели, но он все же предпочтительнее в большинстве ситуаций, потому что он масштабируется намного лучше.

1 голос
/ 28 июня 2009

, если вы можете выполнять 10000000 операций в секунду, то при установке n = 500000 и вычислении n * log (n) = 500 000 * log2 (500 000) = 500 000 * 18 = 9 000 000 операций, что примерно 10 000 000 для целей классификация "секунд".

Аналогично, при n = 3000 вы получите n ^ 2 = 9 000 000. Таким образом, в каждой строке количество операций примерно одинаково.

1 голос
/ 28 июня 2009

Я думаю, что эта таблица дает просто очень приблизительную иллюстрацию того, насколько большим может быть n для различных видов сложностей, когда у вас есть фиксированное время (1 секунда, 1 минута, 1 час, 1 день или 1 год ) в вашем распоряжении.

Например, O (n ^ 3): 

 1 second: 200^3 = 8 000 000 (roughly 10 million, given in O(n) column)
 1 minute: 850^3 = 614 125 000 (roughly 600 million, given in O(n) column))
 1 hour: 3000^3 = 27 000 000 000 (somewhat roughly 35 billion, given in O(n) column)

Как видите, число составляет очень грубых приближений. Кажется, что автор хотел использовать красивые круглые числа, чтобы проиллюстрировать свою точку зрения.

...