Что O (log n) означает точно?

Я узнаю о времени работы Big O Notation и времени амортизации. Я понимаю понятие линейного времени O (n) , означающее, что размер входных данных пропорционально влияет на рост алгоритма ... и то же самое относится, например, к квадратичному времени O (n 2 ) и т.д.

Например, следующая функция - O (n) , потому что алгоритм растет пропорционально его входному значению n :

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

Аналогично, если есть был вложенным циклом, время будет O (n 2 ).

Но что именно O (log n) ? Например, что значит сказать, что высота полного двоичного дерева равна O (log n) ?

Я знаю (может быть, не очень подробно), что такое логарифм, в том смысле, что: log 10 100 = 2, но я не могу понять, как определить функцию с логарифмическим временем.

1926
задан Flimzy 15 July 2019 в 08:29
поделиться