Блог

Главная - Вопросы по программированию - Временная сложность, когда внутренний цикл начинается с j = 2

Временная сложность, когда внутренний цикл начинается с j = 2

#c #time-complexity

#c #временная сложность

Вопрос:

Я получаю O(n^2 logn) в качестве выходных данных следующий код. И все же я не могу понять, почему?

 int unknown(int n) {
    int i, j, k = 0;
    for (i = n / 2; i <= n; i  )
        for (j = 2; j <= n; j = j * 2)
            k = k   n / 2;
    return k;
}

Комментарии:

1. Что вы имеете в виду, когда «получаете O (n ^ 2 logn) в качестве выходных данных следующего кода?» Кто дает вам этот «результат»?

Ответ №1:

Фиксированная постоянная начальная точка не будет иметь никакого значения для внутреннего цикла с точки зрения сложности.

Начинать с двух вместо одного будет означать на одну итерацию меньше, но соотношение по-прежнему логарифмическое.

Подумайте в терминах того, что происходит при удвоении n . Это добавляет еще одну итерацию к этому циклу, независимо от того, начинаете ли вы с одного или двух. Следовательно, это O(log N) сложность.

Однако вы должны иметь в виду, что внешний цикл является O(N) единым, поскольку количество итераций пропорционально N . Это делает функцию в целом O(N log N) , а не O(N2 log N) то, что вы предполагаете.