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

Question

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

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

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

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

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

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

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

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

Answer 1

Я думаю, что эта таблица дает просто очень приблизительную иллюстрацию того, насколько велик 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)

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

Answer 2

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

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

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

Видишь: Обозначение Big O

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

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

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

Answer 3

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

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