Рассчитать большую сложность конкретного алгоритма

Question

Я в настоящее время изо всех сил пытаюсь найти большую сложность O следующего исходного кода:

private static long algo1(long n){
    long counter = 0;
    long i = 1;
    long x = 1;
    while(i < n){
        long a = 4*i;
        for (long j = a; j >= 1; j--) {
            x = x+j;
            counter++;
        }
        i = a/2;
    }
    return counter;
}

Внешний while(i < n) кажется мне сложным log (n).Но какова сложность внутреннего цикла for?

Answer 1

Прежде всего, обратите внимание, что у вас есть встроенный counter, который будет записывать, сколько именно итераций выполняется. Где ваши эксперименты по этому фактору? Как counter реагирует, когда n увеличивается до очень больших чисел? Это, в двух словах, эмпирическое определение сложности.

Рассмотрим цикл , а не просто оператор заголовка. весь цикл управления равен

i = 1
while i < n
    ...
    i *= 2    // i = 4*i / 2

Эквивалент

for (i = 1; i < n; i *= 2)

Таким образом, ваш внутренний цикл действительно O (log2 (n)) .

Во внутреннем цикле x никогда не используется; Вы можете полностью отбросить это вычисление. Все, что делает цикл - это подсчитывает количество итераций.

Вызов подпрограммы с различными значениями n; распечатать результаты.

Answer 2

Внутренний цикл O (i). Если вы рассмотрите шаги, которые он делает, он будет делать 4 при первом запуске, 8 при втором, 16 при третьем ... пока вы не достигнете n. Если вы считаете n степенью 2, чтобы немного упростить математику, 4 + 8 + 16 + ... + n / 4 + n / 2 + n ... будет <= 2n. В общем, ваш алгоритм O (n). </p>