Big-Oh Notation

Question

Я, кажется, смущен вопросом.

Вот вопрос, а затем мои предположения:

Al и Боб спорят о своих алгоритмах. Аль утверждает, что его метод O (n log n) всегда быстрее, чем метод Боба (n^2) -time. Чтобы решить проблему, они проводят ряд экспериментов. К разочарованию Ада они обнаруживают, что если n < 100, алгоритм O (n^2) -time работает быстрее, и только когда n> = 100 является O (n log n) -time лучше. Объясните, как это возможно.

Основываясь на том, что я понимаю, алгоритм, написанный методом O (n^2) -time, эффективен только для небольших количеств ввода n. По мере увеличения ввода эффективность снижается по мере того, как время работы резко возрастает, поскольку время выполнения пропорционально квадрату входа. Метод O (n^2) -time более эффективен, чем метод O (n log n) -time, только для очень малых количеств ввода (в этом случае для входов меньше 100), но по мере увеличения входа (в этот случай 100 или больше), O (n log n) становится гораздо более эффективным методом.

Я только заявляю, что очевидно и представлено в вопросе, или ответ кажется удовлетворительным?

Answer 1

Нет, я думаю, этого недостаточно.

Я бы ожидал ответа, чтобы объяснить, как определение большой-ой позволяет использовать функцию f(x) > g(x), для некоторых x, даже если O(f(x)) < O(g(x)). Там есть формализм, который ответил бы ему в двух строках.

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

Answer 2

Вы правы, если явно рассматриваете ввод, т. Е. N < = 100 и так далее. Но фактически асимптотический анализ (большой O, omega и т. Д.) Выполняется для значительных больших входов, например, когда n стремится к бесконечности. nlogn эффективен, чем n^2. Это утверждение верно, когда n достаточно велико. Мы говорим о большом-о, не учитывая размер ввода. Это означает, что асимптотический анализ по умолчанию предполагает, что размер ввода очень велик. Мы игнорируем конкретные значения n, рассматривая их как зависящие от машины. Вот почему константы игнорируются (поскольку n приближается к достаточно большому, влияние констант становится незначительным)

Answer 3

Ваш ответ верный, насколько это возможно, но в нем не упоминается, как и почему это может произойти. Одно из объяснений состоит в том, что существует фиксированное количество (дополнительных) накладных расходов с помощью метода O (n log n) -time, так что общая выгода метода не суммируется и не превышает накладные расходы до тех пор, пока 100 таких преимуществ не будут агрегированы ,

Answer 4

Вы отметили в своем ответе, что для O (N^2) время выполнения пропорционально к квадрату размера ввода. Следите за этим - существует постоянная пропорциональности, которая присутствует, но не описывается нотой большой O. Для фактических значений времени константы имеют значение.

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

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

Answer 5

По определению:

Т (п) = О (е (п)), если и только если существует две константы С и n0, что: Т (п) < Cf (п) при п> п0.

В ваших случаях это означает, что коэффициенты перед тем п^2 меньше, чем до NlogN или асимптотические пределы могут быть приобретены на п> 100.