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

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

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

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

Точно так же, если бы был вложенный цикл, время было бы O (n2).

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

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

34 ответа

Алгоритмы в парадигме "разделяй и властвуй" имеют сложность O(logn). Одним из примеров здесь, рассчитать свою собственную степенную функцию,

int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}

с http://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

Я хотел бы добавить, что высота дерева - это длина самого длинного пути от корня до листа, а высота узла - это длина самого длинного пути от этого узла до листа. Путь означает количество узлов, с которыми мы сталкиваемся при прохождении дерева между двумя узлами. Чтобы достичь O(log n) временной сложности, дерево должно быть сбалансировано, а это означает, что разность высот между дочерними элементами любого узла должна быть меньше или равна 1. Поэтому деревья не всегда гарантируют временную сложность. O(log n), если они не сбалансированы. На самом деле в некоторых случаях временная сложность поиска в дереве может быть O(n) в худшем случае.

Вы можете взглянуть на деревья баланса, такие как AVL tree, Этот работает для балансировки дерева при вставке данных, чтобы сохранить сложность времени (log n) при поиске в дереве.

Простыми словами:

Следующая итерация цикла занимает вдвое больше времени, чем текущая -> n^2

Следующая итерация цикла занимает столько же времени, сколько и текущая -> n

Следующая итерация цикла занимает половину времени, которое займет текущая -> log2(n)

Следующая итерация цикла занимает 1/3 от времени, которое займет текущий -> log3(n)

Следующая итерация цикла занимает 1/4 от времени, которое займет текущий -> log4(n)

Когда дело доходит до асимптотического анализа, мы просто вызываем log(n), который может быть практически любой базой, как показано выше. Но поскольку мы, информатики, используем бинарные деревья чаще, чем другие типы деревьев, в большинстве случаев мы получаем log2(n), который мы просто называем log(n).

Обозначения Big O Для справки. это может помочь!

Большой O--------------- Сортировка --------------- Сложность

      O(log N)     -Binary search      - logarithmic

O(N)         -Simple search      - Linear

O(N*log N)   -Quicksort          - loglinear 

O(2^N)       -recursive          - Exponential

O(N2)        -Selection sort     - directly proportional to the square of the input size.
Другие вопросы по тегам