Небольшое пояснение Big-O
Действительно ли O(log(log(n))) просто O(log(n)), когда дело доходит до временной сложности?
Согласны ли вы с тем, что эта функция g() имеет временную сложность O(log(log(n)))?
int f(int n) {
if (n <= 1)
return 0;
return f(n/2) + 1;
}
int g(int n) {
int m = f(f(n));
int i;
int x = 0;
for (i = 0; i < m; i++) {
x += i * i;
}
return m;
}
Ответы
Ответ 1
Функция f(n) вычисляет логарифм в базе 2 of n путем многократного деления на 2. Он выполняет итерацию log 2 (n) раз.
Вызов его по собственному результату действительно вернет log 2 (log 2 (n)) для дополнительного log 2 (log 2 (n)).
До сих пор сложность O (log (N)) + O (log (log (N)). Первый член доминирует во втором, общая сложность O (log (N)).
Конечный цикл выполняет итерацию log 2 (log 2 (n)), временная сложность этой последней фазы O (log (log (N)), пренебрежимо мало перед начальной фазой.
Обратите внимание, что поскольку x не используется до конца функции g, вычисление не требуется, и компилятор может оптимизировать этот цикл до нуля.
Общая временная сложность выглядит как O (log (N)), которая не совпадает с O (log (log (N)).
Ответ 2
Похоже, это log(n) + log(log n) + log(log n).
В порядке: первая рекурсия f() плюс вторая рекурсия f() и цикл for, поэтому конечная сложность O (log n), поскольку члены младшего порядка игнорируются.
Ответ 3
int f(int n) {
if (n<=1)
return 0;
return f(n/2) + 1;
}
Имеет временную сложность порядка O(log2(n)). Здесь 2 - основание логрифма.
int g(int n) {
int m = f(f(n)); // O(log2(log2(n))
int i, x=0;
for( i = 0; i < m; i++) {
x += i*i;
}
// This for loop will take O(log2(log2(n))
return m;
}
Следовательно, общая временная сложность заданной функции:
T(n) = t1 + t2 + t3
Но здесь O(log2(n)) доминирует над O(log2(log2(n)).
Следовательно, временная сложность заданной функции log2(n).
Прочтите Что такое простое английское объяснение" Big O " нотация? один раз.
Ответ 4
Время, затрачиваемое на алгоритмы O (log n), зависит только линейно от числа цифр n. Поэтому очень легко масштабировать его.
Предположим, вы хотите вычислить F (100000000), 10 ^ 8th F.... ascci number. Для алгоритма O (log n) он будет принимать только 4 раза за время, затрачиваемое на вычисление F (100).
O (log log n) термины могут отображаться в разных местах, но обычно есть два основных маршрута, которые прибудут в эту среду выполнения. Ссылка здесь введите код здесь.
