Почему не совпадает сложность алгоритма?

Question

[Дмитрий Потылицын]

Всем привет!
Разбираюсь с алгоритмами по Кормену, попутно пытаюсь вспоминать мат. основу из приложений к книге. И нашёл такой пример:

Из вывода, по формуле, ясно-понятно, почему сложность составляет n^2. Но...ведь на практике алгоритм кодируется примерно так:

let result = 0;
for(let i = 1; i <= 3; i++){
   result += i;
}
return result;

И здесь уже сложность составляет - n. Почему? Что я упускаю?

Comments

[Владимир Олохтонов]

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

Answer 1

[Lynn «Кофеман»]

Тут указана не сложность, а асимптотика. Т.е. Сумма натуральных чисел при росте n растёт как n^2

https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1...

Так получилось, что программисты обычно сталкиваются с этими обозначениями только в контексте сложности алгоритмов, но вообще-то это обычная математическая нотация

Comments

[Дмитрий Потылицын]

Сумма натуральных чисел при росте n растёт как n^2

От этой формулировки, складывается впечатление, что при
n = 1, формула Кормена, должна быть равна 1;
n = 2, должна быть равна 4; (на самом деле = 3)
n = 3, должна быть равна 9; (на самом деле = 6)
И т.д.

[Lynn «Кофеман»]

Дмитрий Потылицын, ну почитайте уже по ссылке. «Растёт как» не означает «в точности равно»

[Дмитрий Потылицын]

Всё это я прочитал и ранее. Если бы мне были понятные сухие мат. определения, то, вероятно, здесь бы писать и смысла не было бы )
По правильному, как пишут на вики, "n входит/принадлежит в O(n^2)", что в целом соответствует проиллюстрированный выше в комментарии картине, но...вопросов это, лично для меня, не снимает :(

[Арсений Ефремов]

Это означает, что при увеличении n, (n^2+n)/2 примерно соответствует росту n^2. Если взять n=1e100 то сумма ряда будет примерно равна 5e199, а n^2 = 1e200. Как можно видеть, числа отличаются всего в 2 раза (почти в 2, там еще +5e99, но это очень мало в сравнении).

[Lynn «Кофеман»]

Дмитрий Потылицын, в этом отрывке из книги нет вообще ничего про сложность.
Это кусок про асимптотические оценки.

Сумма натуральных чисел от 1 до n растёт как n² надо понимать так: если мы увеличим n в 10 раз, то сумма увеличится (примерно) в 10² = 100 раз.

[Дмитрий Потылицын]

Как уже говорили выше, разница почти в 2 раза...Как-то тяжело понять, что это несущественно, даже для бесконечных величин...ну да ладно.
Ок...картинка по - тихонечку вырисовывается, почитав другие ответы, побороздив ещё раз книгу...
Тогда, как связать "оценку" (как я понимаю, это то, что ниже Mercury13 назвал "асимптотический порядок многочлена") со "сложностью"?

[Lynn «Кофеман»]

Дмитрий Потылицын, как связать "оценку" со "сложностью"

Никак. Это разные вещи, которые случайно выражаются в одинаковых величинах.

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

[Дмитрий Потылицын]

Алексей Тен, итак...я постараюсь обобщить, всё что удалось узнать в пачку тезисов. Если, в целом, мои догадки верны, то можно закрывать вопрос и потом отмечу решения, что мне помогли.
1. В скриншоте из книги - асимптотическая точная оценка функции, которая говорит что:
1.1. при определённых константах c1 и c2, есть функции c1*f(n) и c2*f(n), которые являются, соответственно, верхней (О-большое) и нижней(о-малое) границей для f(n), т.е. f(n), при наличии определённого множителя, может стремится либо к верхней границе, либо к нижней, но никогда не достигнет их.
1.2. В данном случае, Θ(n^2) (Тета) показывает характер роста функций - парабола. Даже, полагаю, может являться верхней границей. При этом "характер роста", соответственно, сохраняется как для границ, так и для самой функции.
2. Вышеуказанные определения не имеют ничего общего со "сложностью алгоритмов", кроме "нотации О", которая используется для упрощения членов меньшего порядка, определениях худших/лучших случае (верхняя/нижняя граница) и т.д., при анализе сложности алгоритма.
3. "Сложность алгоритма" описывается путём подсчёта необходимого количества инструкций в конкретной реализации (коде).
---
Прошу поправить, если есть неточности, или может какие-то ещё важные нюансы, которые могут пригодится и о которых я забыл отписать? Заранее, спасибо.

[Lynn «Кофеман»]

Ну в общем всё примерно так.

> 3. "Сложность алгоритма" описывается путём подсчёта необходимого количества инструкций в конкретной реализации (коде).

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

[Дмитрий Потылицын]

Да, это ясно-понятно. Ладно, спасибо за разъяснение, как и всем принимавшим участие!

Answer 2

[Руслан .]

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

Comments

[Дмитрий Потылицын]

Понятно. Тогда почему Кормен пишет о второй степени, если ни в одном случае, на практике (по приведённым методам: цикл и формула), выйти на этот порядок не удаётся?

Answer 3

[Mercury13]

Это так называемая асимптотическая сложность — сложность при n→∞.

Что никто не упомянул — так называемые символы Ландау.
a(n) = o(b(n)), (читается «о малое», «меньшего порядка чем»), если lim{n→∞}a/b = 0
a(n) = O(b(n)), (читается «о большое», «не большего порядка чем»), если a/b ограничено сверху (для дискретного n этого хватит, для непрерывного надо добавить «для какого-то n>N»).

Два символа Дональда Кнута дополняют символы Ландау.
a(n) = Ω(b(n)), если b(n) = O(a(n)). «Не меньшего порядка чем»
a(n) = Θ(b(n)), если a(n) = O(b(n)) и b(n) = O(a(n)). «Такого же порядка».

Ну а дальше идут простые пределы.
• axⁿ + bxⁿ⁻¹ + … = O(cx^k + dx^k−1 + …), если n ≤ k;
• те же два многочлена o(·), если n < k.
• те же два многочлена Θ(·), если n = k.
Константа не важна: во-первых, при n→∞ меньшая сложность рано или поздно перевесит меньшую константу. Во-вторых, особенности реализации того или иного алгоритма на том или ином компиляторе/железе (больше/меньше команд, лучше/хуже с кэшем) эту константу могут варьировать в широких пределах;

А значит, многочлен n(n−1)/2 = n²/2 − n/2 = Θ(n²).

Да, и ещё: вы спутали асимптотический порядок самогó многочлена и асимптотическую сложность его вычисления. Первое, как я уже сказал, n². Сложность вычисления в лоб — n+const = O(n). А «не в лоб» — «за константу» , O(1).