Вопрос по теории алгоритмов. Оценка сложности алгоритма

[KostyaTuch]

Здравствуйте, в книге "Величайшие математические задачи" я нашёл оценку сложности $O(\log\log n)$. Что обозначает эта сложность? И какая разница между оценкой сложности $O(\log\log n)$ и $O(\log n)$?

[lel0lel]

А как вы понимаете сложность $O(f(n) )$?

[Dmitriy40]

Например умножение числа в формате плавающей точки $n=a.aa \cdot b^{ccc}$ на степень основания системы счисления $y=b^k$ сводится к сложению чисел $ccc+k$, что выполняется за примерно $\log (ccc+k)$, или порядка $\log \log n$ при $k \ll ccc$. Вот и ваша сложность.

[KostyaTuch]

lel0lel в сообщении #1503518 писал(а):

А как вы понимаете сложность $O(f(n) )$?

Я новичок в этой теме, так что я могу понимать неправильно.
Сложность $O(f(n) )$ означает, что время работы алгоритма зависит только от количества входных данных.

[lel0lel]

Не совсем, от самих данных время работы также может зависеть. Это надо понимать так: для достаточно больших $n$ найдётся такая константа $C$, что число операций производимых при выполнении алгоритма не превосходит $C f(n).$ Каких именно операций надо уточнять дополнительно, не всегда элементарных. Время работы алгоритма, конечно, связано с числом операций.

[KostyaTuch]

lel0lel в сообщении #1503522 писал(а):

Не совсем, от самих данных время работы также может зависеть. Это надо понимать так: для достаточно больших $n$ найдётся такая константа $C$, что число операций производимых при выполнении алгоритма не превосходит $C f(n).$ Каких именно операций надо уточнять дополнительно, не всегда элементарных. Время работы алгоритма, конечно, связано с числом операций.

Спасибо, учту.

[Geen]

Dmitriy40 в сообщении #1503519 писал(а):

Вот и ваша сложность.

Конечно нет - $n$ означает размер данных.

[arseniiv]

Хотел вчера помянуть ради интереса сложность $O(F(x))$, где $F$ — обратная к функции Аккермана (такая сложность возникает для какого-то алгоритма и её натурально заменяют в дальнейших оценках на константную), но тема пошла веселее.

[mihaild]

(Оффтоп)

arseniiv в сообщении #1503732 писал(а):

такая сложность возникает для какого-то алгоритма

Для леса непересекающихся множеств. Там очень забавное доказательство, имеющее вид "почти вся работа делается в поддереве рядом с корнем - так что сложность не больше чем логарифмическая; а в этом поддереве почти вся работа опять делается рядом с корнем - так что сложность не больше чем двойной логарифм; а в этом поддереве опять вся работа рядом с корнем ...". Я когда-то проследил за этой логикой до $\log^*$, но дальше осознать не смог.

[Skipper]

lel0lel в сообщении #1503518 писал(а):

А как вы понимаете сложность $O(f(n) )$?

$n$ - это так сказать, некая мера входных данных, для алгоритма. Это не обязательно может быть численность каких то элементов, над которыми будет работать алгоритм. Пример подобной задачи - провести сортировку в массиве из $n$ элементов.
Вот задача например, факторизовать , т.е. разложить некое число на множители. Чем больше число, тем больше его длина записи - $n$ цифр (знаков).

И сложность (трудоёмкость) алгоритмов может быть 1) экспоненциальной от $n$, 2) субэкспоненциальной, 3) полиномиальной, 4) линейной или $O(n \ln n)$ , 5) логарифмической, т.е. $O(\ln n)$ .

Пример 1-го - факторизация числа путем перебора делителей, 2-го - факторизация числа методом эллиптических кривых, 3-го - проверить, простое число или составное, 4-го - сортировка массива, или поиск элемента в массиве, 5-го - поиск элемента в сбалансированном дереве.