Сложность этой функции?

Question

void compute(int n) {
        int h = n;
        while (h > 1) {
            for (int i = 0; i < n; i++) {
                // do some operation
            }
            h = h / 2;
        }
 }

Может кто-нибудь сказать, пожалуйста, какова сложность (Big O) этой функции n ??

Это на самом деле спор между мной и моим другом. моя позиция: сложность O (n * log (n)) стенд друга: log (n)

Спасибо за ваши ответы.

Answer 1

Я бы сказал, потому что в каждом прогоне h делится на два и n операций выполняется, это O (n * log n).

Answer 2

Если это домашнее задание (и оно звучит немного похоже), то сначала вы должны попробовать себя.

В основном, чтобы получить полноту, вы смотрите на структуру функции, то есть циклы, вложенные циклы и т. Д., И определяете, как долго они работают, от каких входов они зависят и т. Д.

В этом случае у вас есть только один вход, n . Локальная переменная h начинается с того же значения, что и n , поэтому она по сути такая же, с точки зрения сложности, однако вам необходимо отслеживать, как она используется.

Здесь у вас есть два вложенных цикла, один из которых работает на n , другой - вокруг него, в результате чего h уменьшается вдвое при каждом запуске. Так что эта функция в O ( n · log ₂ n ).

Answer 3

Некоторые операции:

O(x)

Цикл for: потому что n> = h и предположим, что h не будет изменен во время «некоторой операции»:

O(n*x)

Внешний цикл while:

O(log(n)*n*x)

Answer 4

Это явно n * log (ч) .

Answer 5

Похоже, что O (n.sqrt (n))

Внешний цикл, очевидно, равен n, а внутренний цикл - sqrt (n).

РЕДАКТИРОВАТЬ: внутренний цикл правильно log (n), потому что число итераций х, где 2 ^ x = n.