Что ассимптотически сложнее — линейная или квадрат логарифма?

Question

[uvelichitel]

O(n) или O((log n)**2), что больше?

Answer 1

[shurshur]

Открываем Wolfram Alpha, вводим n или (log n)^2 или даже n/(log n)^2 и сразу получаем ответ: линейная сложнее.

Comments

[uvelichitel]

Спасибо, у меня нет Wolfram)

[shurshur]

uvelichitel, это просто сайт :) Но можно было бы любой другой рисовальщик графиков использовать.

[uvelichitel]

Из рисовальщиков графиков у меня gnuplot на машине установлен и как там ввести (log n)^2 и даже просто как ввести log по основанию умишка/опыта не хватает) Я разработчик все же больше чем математик.

[rPman]

uvelichitel, тут не нужен ум, нужна документация

[Александр Скуснов]

uvelichitel, Для асимптотики основание роли не играет. У американцев log это наш ln (основание e, натуральный логарифм), lg (десятичного) обычно нет, но есть log10, log2.

[Дмитрий Беляев]

Для асимптотики основание роли не играет.

Александр Скуснов, всегда считал, что в асимптотике именно log2 используется, так как он ложится на двоичную СС примерно так же как log10 на десятеричную.
Ну и если руками посчитать сложность для merge sort например или бинарного поиска, то там именно логарифмы по основанию 2 выходят

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

Дмитрий Беляев, изменение основания логарифма это просто умножение на константу. Поскольку в асимптотике константы неважны, то и основание логарифма неважно.

Поэтому когда говорят «логарифмическая сложность» никто не уточняет основание.