Я дізнаюся про час виконання та амортизований час у системі числення 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)?
Я знаю (можливо, не дуже детально), що таке логарифм, в тому сенсі, що: log10100 = 2, але не можу зрозуміти, як ототожнити функцію з логарифмічним часом.
Логарифмічний час виконання (O(log n)
) по суті означає, що час виконання зростає пропорційно логарифму розміру вхідних даних - як приклад, якщо 10 елементів займає не більше деякої кількості часу x
, а 100 елементів займає не більше, скажімо, 2x
, а 10 000 елементів займає не більше 4x
, то це виглядає як O(log n)
часова складність.
Це просто означає, що час, необхідний для виконання цього завдання, зростає з log(n) (наприклад: 2 с для n = 10, 4 с для n = 100, ...). Для більшої точності читайте статті Вікіпедії про Алгоритм двійкового пошуку та Нотація Big O.