Хорошо, поэтому у меня есть этот проект, который я должен сделать, но я просто этого не понимаю. Дело в том, что у меня есть 2 алгоритма. O (n ^ 2) и O (n * log 2 n).
В любом случае, я узнаю в информации о проекте, что если n < 100, то O (n ^ 2) более эффективен, но если n >= 100, то O (n * log 2 n) более эффективен. Я должен продемонстрировать пример, используя цифры и слова или нарисовать фотографию. Но дело в том, что я не понимаю этого, и я не знаю, как это продемонстрировать.
Кто-нибудь может помочь мне понять, как это работает?
Приветствуем заранее!
EDIT: Спасибо всем за ответы.
Просто спросите wolframalpha, если у вас есть сомнения.
В этом случае говорится:
n log(n)
lim --------- = 0
n^2
Или вы также можете сами рассчитать лимит:
n log(n) log(n) (Hôpital) 1/n 1
lim --------- = lim -------- = lim ------- = lim --- = 0
n^2 n 1 n
Это означает, что n^2 растет быстрее, поэтому n log(n) меньше (лучше), когда n достаточно высок.
Итак, O(N*log(N)) намного лучше, чем O(N^2). Он намного ближе к O(N), чем к O(N^2).
Но ваш алгоритм O(N^2) работает быстрее N < 100 в реальной жизни. Есть много причин, почему это может быть быстрее. Возможно, из-за лучшего выделения памяти или других "неагрессивных" эффектов. Может быть, алгоритм O(N*log(N)) требует некоторой фазы подготовки данных или O(N^2) итераций короче. Во всяком случае, запись Big-O подходит только в случае достаточно больших Ns.
Если вы хотите продемонстрировать, почему один алгоритм работает быстрее для небольших Ns, вы можете измерить время выполнения 1 итерации и постоянные накладные расходы для обоих алгоритмов, а затем использовать их для коррекции теоретического графика:
Или просто измерить время выполнения обоих алгоритмов для разных Ns и построить эмпирические данные.
Обозначение Big-O является обозначением асимптотической сложности. Это означает, что он вычисляет сложность, когда N сколь угодно велико.
При малых Ns возникает множество других факторов. Возможно, что алгоритм имеет итерации цикла O (n ^ 2), но каждая итерация очень короткая, а в другом алгоритме есть итерации O (n) с очень длинными итерациями, При больших Ns линейный алгоритм будет быстрее. При малых Ns квадратичный алгоритм будет быстрее.
Итак, для маленьких Ns просто измерьте два и посмотрите, какой из них быстрее. Нет необходимости входить в асимптотическую сложность.
Кстати, не записывайте основы журнала. Нотация Big-O игнорирует константы - O (17 * N) совпадает с O (N). Так как log 2 N просто ln N / ln 2, базис логарифма является просто другой константой и игнорируется.
Давайте сравним их,
С одной стороны, мы имеем:
n^2 = n * n
С другой стороны, мы имеем:
nlogn = n * log(n)
Поместив их сбоку:
n * n versus n * log(n)
Разделим на n, который является общим термином, чтобы получить:
n versus log(n)
Давайте сравним значения:
n = 10 log(n) ~ 2.3
n = 100 log(n) ~ 4.6
n = 1,000 log(n) ~ 6.9
n = 10,000 log(n) ~ 9.21
n = 100,000 log(n) ~ 11.5
n = 1,000,000 log(n) ~ 13.8
Итак, мы имеем:
n >> log(n) for n > 1
n^2 >> n log(n) for n > 1
Во-первых, не совсем корректно сравнивать асимптотическую сложность, смешанную с N-ограничением. Я., могу утверждать:
O(n^2) медленнее, чем O(n * log(n)), потому что определение нотации Big O будет включать n is growing infinitely.
Для конкретного N можно сказать, какой алгоритм быстрее, просто сравнивая N^2 * ALGORITHM_CONSTANT и N * log(N) * ALGORITHM_CONSTANT, где ALGORITHM_CONSTANT зависит от алгоритма. Например, если мы дважды пройдем массив, чтобы выполнить нашу работу, асимптотическая сложность будет O(N), а ALGORITHM_CONSTANT будет 2.
Также я хотел бы упомянуть, что O(N * log2N), который я предполагаю, логарифм на основе 2 (log 2 N) на самом деле тот же, что и O(n * log(n)) из-за свойств логарифма.
У нас есть два способа сравнить два Algo - > первый способ - очень просто сравнить и применить предел
T1(n)-Algo1
T2(n)=Alog2
lim (n->infinite) T1(n)/T2(n)=m
(i), если m = 0 Algo1 быстрее, чем Algo2
(ii) m = k Оба одинаковы
(iii) m = бесконечный Algo2 быстрее
* Второй путь довольно прост, так как сравним с 1-м там, вы просто берете журнал обоих, но не игнорируете multi constant
Algo 1=log n
Algo 2=sqr(n)
keep log n =x
Any poly>its log
O(sqr(n))>o(logn)