Расчет сложности алгоритма

Question

Я не уверен, что это правильный вопрос.

Давайте предположим, что существует алгоритм O (n ^ 3), который сортирует 100 чисел в день с вычислительной мощностью x.

Сколько чисел он сможет отсортировать, если вычислительная мощностьвдвое, т.е. 2x.

Я понимаю, что я не определяю «вычислительную мощность».Пожалуйста, исправьте вопрос, если он двусмысленный или неправильный.

Answer 1

Обозначение Big O не дает точного времени (реального времени компьютера).Это метод, который пытается понять эффективность алгоритмов, не зависящих от процессора или других специфических особенностей компьютера.

В отношении математики можно сказать, что O (n ^ 2) более эффективно, чем O (n ^ 3),Но с точки зрения инженера, для некоторых значений n O (n ^ 3) может быть лучше, чем O (n ^ 2).Этот метод просто говорит, что для достаточно большого n O (n ^ 2) будет более эффективным, чем O (n ^ 3).

Существует хорошее введение в алгоритм анализа в вашей пробирке.Первая глава хороша для объяснения этих вещей: MIT 6.046J / 18.410J Введение в алгоритмы

Обозначение Big O может говорить только то, что для той же машины, для достаточно больших n, O (п ^ 2) лучше, чем О (п ^ 3).Но для того же алгоритма я думаю, что вы не можете сделать прямое предложение между мощностью и выходом компьютера. Если мы удвоим мощность компьютера, выход удвоится? Может быть, да, но может и нет. Я думаю, что мы не можем сказать такую ​​вещь, просто посмотрев алгоритм Big O.

Answer 2

N = 100 может быть недостаточно большим, чтобы можно было предположить, что алгоритм уже достиг своего асимптотического поведения с точки зрения использования ЦП, поэтому использование большого выражения O для экстраполяции использования ЦП для больших наборов данных может привести к ошибочным результатам.

Хотя вы можете попытаться определить, находитесь ли вы уже в асимптотической зоне, измерить загрузку ЦП для наборов данных других размеров (например, 50, 80, 120 и т. Д.) И посмотреть, как они помещаются на * 1003. * кривая, являющаяся константой C, подлежащей определению.

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

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

Обновление : в ответ на сообщение Vapuru и его комментарии:

Для типичного алгоритма O (N ^ 3) количество операций, выполняемых конкретной реализацией, составляет t = a + b * N + c * N^2 + d * N^3 (могут быть и другие компоненты, например log N, но, как вы увидите, это на самом деле не имеет значения ). Таким образом, для двух заданных наборов данных размером N1 и N2 можно рассчитать t1 и t2 соответственно.

Для данной задачи ОП t2 / t1 = 2, поэтому (a + b * N2 + c * N2^2 + d * N2^3) / (a + b * N1 + c * N1^2 + d * N1^3) = 2, а для N1 и N2 достаточно большой, чтобы выражение можно было аппроксимировать как (d * N2^3)/(d * N1^3) = 2, которое можно еще более упростить до (N2/N1)^3 = 2 и т. Д. N2 = N1 * 2^(1/3).

Это означает, что для больших наборов данных удвоение времени обработки (или удвоение скорости обработки и сохранение неизменного времени) позволяет приблизительно увеличить размер набора данных в 2^(1/3), то есть 1.26 или %.

На практике другие факторы, помимо скорости процессора, могут влиять на производительность, поэтому на самом деле это следует читать как N2/N1 < 1.26.