Большой вопрос о алгоритме с (n ^ 2 + n) / 2 скоростью роста

16

Я задаю этот вопрос, потому что я запутался в одном аспекте, касающемся обозначения больших О.

Я использую книгу Фрэнка Каррано « Структуры данных и абстракции с Java ». В главе «Эффективность алгоритмов» он показывает следующий алгоритм:

int sum = 0, i = 1, j = 1
for (i = 1 to n) {
    for (j = 1 to i)
        sum = sum + 1
}

Первоначально он описывает этот алгоритм как имеющий скорость роста (n 2  + n) / 2 . Который смотрит на это кажется интуитивным.

Однако затем утверждается, что (n 2  + n) / 2 ведет себя как n 2, когда n большое. В том же абзаце он утверждает (п 2  + п) / 2 также ведет себя так же, как п 2 / 2 . Он использует это, чтобы классифицировать вышеупомянутый алгоритм как O (n 2 ) .

Я получаю , что (п 2  + п) / 2 аналогично п 2 / 2 , так как в процентном отношении, п имеет небольшое значение. Я не понимаю, почему (n 2  + n) / 2 и n 2 похожи, когда n большое.

Например, если n = 1 000 000 :

(n^2 + n) / 2 =  500000500000 (5.000005e+11)
(n^2) / 2     =  500000000000 (5e+11)
(n^2)         = 1000000000000 (1e+12)

Этот последний не похож на всех. На самом деле, совершенно очевидно, что он вдвое больше среднего. Так как же Фрэнк Каррано сказать, что они похожи? Кроме того, как алгоритм классифицируется как O (n 2 ) . Глядя на этот внутренний цикл, я бы сказал, что это n 2 + n / 2

Эндрю С
источник
Если вам интересно, я дал ответ для трех вложенных циклов с проверкой диаграммы дерева выполнения. Головоломка, связанная с вложенными циклами
Grijesh Chauhan
1
в основном идея заключается в том, что по мере nроста функции 'n ^ 2` и ваша функция ведут себя одинаково, что приводит к постоянной неуверенности в скорости их роста. Если у вас сложное выражение, функция, которая растет быстрее, доминирует.
AK_
1
@MichaelT: я не думаю, что это дубликат этого вопроса, так как другой - просто неправильный подсчет. Это более тонкий вопрос о том, почему игнорируются меньшие члены (в частности, постоянные множители и полиномы более низких степеней). Спрашивающий здесь, очевидно, уже понимает проблему, поднятую в другом вопросе, и ответ, достаточный для этого вопроса, не даст ответа на этот вопрос.
Сденхэм

Ответы:

38

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

Если у вас есть сложный алгоритм, (n^2 + n)/2и вы удваиваете количество элементов, то константа 2не влияет на увеличение времени выполнения, термин nвызывает удвоение времени выполнения, а термин n^2вызывает четырехкратное увеличение времени выполнения. время.
Поскольку n^2термин имеет наибольший вклад, сложность Big-O равна O(n^2).

Барт ван Инген Шенау
источник
2
Мне нравится это, это становится немного яснее.
Эндрю С
7
Это очень волнистая рука. Может быть правдой или ложью. Если вы можете взять немного математики, посмотрите один из ответов ниже.
USR
2
Это рассуждение слишком расплывчато: это означало бы, что мы могли бы сделать вывод O(n * log n) = O(n), что это не так.
cfh
Возможно, это не самый точный или семантически правильный ответ, но здесь важно то, что он заставил меня начать понимать суть, и я думаю, что это была цель автора. Это намеренно расплывчато, поскольку детали часто отвлекают от основных принципов. Важно видеть лес за деревьями.
Андрей С
Барт действительно говорил о терминах, а не о факторах. Понимая это, мы не можем сделать вывод O(n * log n) = O(n). Я думаю, что это дает хорошее объяснение обоснования определения.
Марк Фоски
10

Определение таково, что

f(n) = O(g(n))

если существует некоторая постоянная C> 0 такая, что для всех n, больших n_0, имеем

|f(n)| <= C * |g(n)|

Это очевидно верно для f (n) = n ^ 2 и g (n) = 1/2 n ^ 2, где константа C должна быть 2. Также легко видеть, что это верно для f (n) = n ^ 2 и g (n) = 1/2 (n ^ 2 + n).

CFH
источник
4
«Если существует некоторая константа C> 0 такая, что для всех n,« должно быть »Если существует какая-то константа C, n_0 такая, что для всех n> n_0»,
Таемир,
@Taemyr: Пока функция gненулевая, это на самом деле не нужно, так как вы всегда можете увеличить константу C, чтобы сделать утверждение истинным для конечного числа первых значений n_0.
cfh
Нет, пока мы смотрим на функции, не существует конечного числа потенциальных значений n_0.
Taemyr
@Taemyr: n_0 - конечное число. Выберите C = max {f (i) / g (i): i = 1, ..., n_0}, и тогда оператор всегда будет выполняться для первых значений n_0, что вы можете легко проверить.
cfh
В CS это менее важно, потому что n обычно является размером ввода и, следовательно, небезрассуден. В этом случае можно выбрать C таким, что n_0 = 1 работает. Но формальное определение - это любой n, превышающий некоторый порог, который устраняет много недоразумений при применении определения.
Taemyr
6

Говоря о сложности, вас интересуют только изменения временного фактора в зависимости от количества элементов ( n).

Таким образом, вы можете удалить любой постоянный фактор (как 2здесь).

Это оставляет вас с O(n^2 + n).

Теперь, для достаточно большого nпродукта, т. Е. n * nБудет значительно больше, чем просто n, что является причиной, по которой вам также разрешено пропустить эту часть, что оставляет вас действительно с окончательной сложностью O(n^2).

Это правда, для небольших чисел будет существенное различие, но оно становится тем незначительнее, чем больше вы nстановитесь.

Марио
источник
Насколько велика должна быть разница, чтобы разница стала маргинальной? Кроме того, почему / 2 удален, его существование уменьшает значение вдвое?
Эндрю С
6
@AndrewS Потому что Big O Notation говорит о росте. Деление на 2 не имеет значения вне контекста тестов и временных отметок, потому что в конечном итоге оно не меняет темп роста. Однако самый большой компонент делает, и это все, что вы оставляете.
Нил
2
@ Ниль, молодец, так ясно. Я бы хотел, чтобы в книгах было так. Иногда я думаю, что авторы слишком много знают о том, что они забывают о том, что простые смертные не обладают своим функциональным знанием и, следовательно, не дают четких важных замечаний, а вместо этого скрывают это в каком-то формальном математическом описании или опускают все вместе, полагая, что это подразумевается.
Андрей С
Хотелось бы, чтобы я мог проголосовать за этот ответ более одного раза! @ Нил, ты должен писать книги о Большой О.
Терсосаврос
3

Дело не в том, что «(n² + n) / 2 ведет себя как n², когда n большое», а в том, что (n² + n) / 2 растет какпри увеличении n .

Например, при увеличении n от 1000 до 1000000

(n² + n) / 2  increases from  500500 to  500000500000
(n²) / 2      increases from  500000 to  500000000000
(n²)          increases from 1000000 to 1000000000000

Точно так же, как n увеличивается от 1 000 000 до 1 000 000 000

(n² + n) / 2  increases from  500000500000 to  500000000500000000
(n²) / 2      increases from  500000000000 to  500000000000000000
(n²)          increases from 1000000000000 to 1000000000000000000

Они растут так же, как и в Big O Notation.

Если вы нанесете (n² + n) / 2 и n² / 2 на Wolfram Alpha , они настолько похожи, что их трудно различить по n = 100. Если вы нанесете все три на Wolfram Alpha , вы увидите две линии, разделенные постоянным множителем 2.

ShadSterling
источник
Это хорошо, это очень ясно для меня. Спасибо за ответ.
Андрей С
2

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

Как вы знаете, это обозначение выражает асимптотическое сравнение функций, и запись f = O (g) означает, что f (n) растет не более, чем g (n), так как n уходит в бесконечность. Простой способ перевести это - сказать, что функция f / g ограничена. Но, конечно, мы должны заботиться о тех местах , где г равно нулю, и мы получим более надежное определение, которое вы можете прочитать почти везде .

Эти обозначения оказываются очень удобными для вычислений - вот почему они так широко распространены - но с ними следует обращаться осторожно, поскольку знак равенства, который мы видим там, не обозначает равенство функций . Это очень похоже на то, что 2 = 5 мод 3 не означает, что 2 = 5, и если вы увлекаетесь алгеброй, вы можете реально понимать обозначение большой О как равенство по модулю чего-то.

Теперь, чтобы вернуться к вашему конкретному вопросу, совершенно бесполезно вычислять несколько числовых значений и сравнивать их: каким бы большим ни был миллион, он не учитывает асимптотическое поведение. Было бы более полезно изобразить соотношение функций f (n) = n (n-1) / 2 и g (n) = n² - но в этом частном случае мы легко видим, что f (n) / g (n) меньше 1/2, если n> 0, что означает, что f = O (g) .

Чтобы улучшить ваше понимание обозначений, вы должны

  • Работайте с четким определением, а не с нечетким впечатлением, основанным на похожих вещах - как вы только что это испытали, такое нечеткое впечатление не сработает.

  • Потратьте некоторое время, чтобы детально проработать примеры. Если вы отработаете всего пять примеров за неделю, этого будет достаточно, чтобы повысить вашу уверенность. Это усилие, которое определенно стоит.


Замечание об алгебре. Если A - алгебра всех функций Ν → Ν, а C - подалгебра ограниченных функций, то для данной функции f множество функций, принадлежащих O (f), является C -подмодулем A , и правила вычисления на большом Обозначения O просто описывают, как A работает с этими подмодулями. Таким образом, равенство, которое мы видим, является равенством C -подмодулей A , это просто еще один вид модуля.

Михаэль Ле Барбье Грюневальд
источник
1
За этой статьей в Википедии трудно проследить после первой небольшой кусочки. Он был написан для опытных математиков опытным математиком и не является тем вводным текстом, который я ожидал бы из энциклопедической статьи. Спасибо за ваше понимание, хотя все хорошо.
Андрей С
Вы переоцениваете уровень в тексте Википедии! :) Это не так хорошо написано, конечно. Грэм, Кнут и Паташник написали прекрасную книгу «Конкретная математика» для студентов CS. Вы также можете попробовать «Искусство компьютерного программирования» или книгу по теории чисел, написанную в 50-х годах (Hardy & Wright, Rose), поскольку они обычно ориентированы на уровень старшеклассников. Вам не нужно читать всю книгу, если вы ее выберете, только часть об асимптотике! Но прежде чем решить, сколько вам нужно понять. :)
Михаэль Ле Барбье Грюневальд
1

Я думаю, вы неправильно понимаете, что означает большая буква О.

Когда вы видите O (N ^ 2), это в основном означает: когда проблема становится в 10 раз больше, время ее решения будет: 10 ^ 2 = в 100 раз больше.

Давайте пробьём 1000 и 10000 в вашем уравнении: 1000: (1000 ^ 2 + 1000) / 2 = 500500 10000: (10000 ^ 2 + 10000) / 2 = 50005000

50005000/500500 = 99,91

Таким образом, в то время как N увеличился в 10 раз, решения выросли в 100 раз. Следовательно, он ведет себя: O (N ^ 2)

Питер Б
источник
1

если п был 1,000,000тогда

(n^2 + n) / 2  =  500000500000  (5.00001E+11)
(n^2) / 2      =  500000000000  (5E+11)
(n^2)          = 1000000000000  (1E+12)

1000000000000.00 что?

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

Это дает нам степень пропорции.

Если алгоритм должен что-то делать n² раз, то для некоторого значения c, то есть того, сколько времени занимает каждая итерация, потребуется n² × c.

Если алгоритм должен что-то делать n² ÷ 2 раза, то для некоторого значения c, которое в два раза дольше, чем для каждой итерации, потребуется n² × c.

В любом случае, затраченное время все еще пропорционально n².

Теперь эти постоянные факторы нельзя игнорировать; действительно, у вас может быть случай, когда алгоритм со сложностью O (n²) работает лучше, чем алгоритм со сложностью O (n), потому что если мы работаем над небольшим количеством элементов, то влияние сопутствующих факторов будет больше и может преодолеть другие проблемы , (Действительно, даже O (n!) Совпадает с O (1) для достаточно низких значений n).

Но это не то, о чем говорит нам сложность.

На практике есть несколько способов улучшить производительность алгоритма:

  1. Повышение эффективности каждой итерации: O (n²) по-прежнему выполняется за n² × c секунд, но c меньше.
  2. Уменьшите количество наблюдаемых случаев: O (n²) все еще выполняется за n² × c секунд, но n меньше.
  3. Замените алгоритм на тот, который имеет те же результаты, но с меньшей сложностью: например, если бы мы могли изменить что-то O (n²) на что-то O (n log n) и, следовательно, изменить его с n² × c₀ секунд на (n log n) × c₁ секунд ,

Или, если посмотреть по-другому, у нас есть f(n)×cнесколько секунд, и вы можете улучшить производительность, уменьшив c, уменьшив nили уменьшив fдоходность для данногоn .

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

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

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

При практическом использовании меры сложности позволяют нам рассуждать о различиях между алгоритмами именно потому, что они игнорируют вопрос о том, как поможет уменьшение n или c, чтобы сосредоточиться на рассмотрении f()

Джон Ханна
источник
«O (n!) - это то же самое, что O (1) для достаточно низких значений n» - просто неправильно. Должен быть лучший способ объяснить, что «когда значение nдостаточно низкое, значение Big-O не имеет значения».
Бен Фойгт
@BenVoigt Мне еще не приходилось сталкиваться с таким же риторическим воздействием, каким оно было при первом прочтении; это изначально не мое, я украл его у Эрика Липперта, который, возможно, его создал или, возможно, взял у кого-то другого. Конечно, он ссылается на шутки, такие как «π равно 3 для малых значений π и больших значений 3», который еще старше.
Джон Ханна
0

Постоянный фактор

Смысл больших обозначений O заключается в том, что вы можете выбрать произвольно большой постоянный множитель, чтобы O (function (n)) всегда было больше, чем C * function (n). Если алгоритм A в миллиард раз медленнее, чем алгоритм B, то они имеют одинаковую сложность O, если эта разница не увеличивается, когда n растет сколь угодно большим.

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

(n ^ 2 + n) / 2 «вписывается в» O (n ^ 2), потому что для любого n, независимо от его размера, (n ^ 2 + n) / 2 <1000000 * n ^ 2.

(n ^ 2 + n) / 2 «не подходит» меньшему набору, например, O (n), потому что для некоторых значений (n ^ 2 + n) / 2> 1000000 * n.

Постоянные факторы могут быть сколь угодно большими - алгоритм со временем выполнения n лет имеет сложность O (n), которая "лучше", чем алгоритм со временем работы n * log (n) микросекунд.

Петерис
источник
0

Big-O - все о том, насколько сложен алгоритм. Если у вас есть два алгоритма, и одному требуется n^2*kнесколько секунд для запуска, а другому - n^2*jсекунды, то вы можете поспорить о том, какой из них лучше, и вы можете сделать некоторые интересные оптимизации, чтобы попытаться повлиять kили j, но оба эти алгоритмы очень медленные по сравнению с алгоритмом, который требуется n*mдля запуска. Неважно, насколько малы вы делаете константы, kили j, если вход достаточно большой, n*mалгоритм всегда выиграет, даже еслиm он достаточно велик.

Итак, мы называем первые два алгоритма O(n^2)и называем второй O(n). Он красиво делит мир на классы алгоритмов. Это то, что Big-O это все. Это похоже на разделение транспортных средств на легковые и грузовые автомобили, автобусы и т. Д. Между автомобилями много различий, и вы можете провести целый день, споря о том, лучше ли Prius, чем Chevy Volt, но в конце дня, если вы нужно собрать 12 человек в один, тогда это довольно бессмысленный аргумент. :)

Джейсон Уолтон
источник