Вложность сложного времени L oop Внутренний L oop + Внешний цикл

Question

Кто-нибудь может объяснить, какова сложность времени для этого алгоритма?

for (i = 1; i <= n; i++){
    for(j = 1; j <= n; j += i) {   // note: not j++
        printf("Iteration %d : %d\n", i, j);   
    }
}

Answer 1

printf во внутреннем l oop называется ровно ceil(n) + ceil(n/2) + ceil(n/3) + ... ceil(n/n) раз. Чтобы избавиться от ceil, мы знаем, что ceil(y/n) ограничен сверху y/n + 1, поэтому мы знаем, что число выполнений >= n + n/2 + n/3 ... n/n, но < n + 1 + n/2 + 1 + n/3 + 1 + n/4 + 1... + n/n + 1. Первое может быть учтено до n(1 + 1/2 + 1/3 + 1/4 ... 1/n), а второе может быть рефакторизовано в n(1 + 1/2 + 1/3 + 1/4 ... 1/n) + n.

Последний фактор имеет первое прибавление к бесконечности - это гармоника c ряд , который расходится. Известно, что сумма первых k терминов со страницы Википедии ограничена:

, что означает, что 1 + 1/2 + 1/3 + 1/4 ... 1/n равно Ө(ln n) = Ө(log n); мы можем дать строгие ограничения на количество вызовов printf (c(n): n log n <= c(n) < n log n + 2n. Поскольку n log n растет быстрее, чем 2n, мы можем оставить только первое и заметить, что обе границы принадлежат Ө(n log n) и, следовательно, c(n) также относится к Ө(n log n) (Ө(F) означает, что функция одновременно Ω(F) и O(F)) .

Answer 2

Другой способ проанализировать сложность состоит в том, чтобы выяснить, сколько еще итераций добавляется, если вы удвоите n.

for (i = 1; i <= 2*n; i++){
    for(j = 1; j <= 2*n; j += i) {   // note: not j++
        printf("Iteration %d : %d\n", i, j);   
    }
}

. Это можно разбить на два цикла:

for (i = 1; i <= n; i++){
    for(j = 1; j <= 2*n; j += i) {   // note: not j++
        printf("Iteration %d : %d\n", i, j);   
    }
}

for (i = n+1; i <= 2*n; i++){
    for(j = 1; j <= 2*n; j += i) {   // note: not j++
        printf("Iteration %d : %d\n", i, j);   
    }
}

В первом l oop это выглядит как оригинальное l oop, но внутренний размер l oop удвоился. Итак, первый l oop выполняется вдвое дольше, чем исходный алгоритм.

Для второго l oop время выполнения равно O (n), поскольку внутренний l oop выполняет 2 итерации для каждое значение i (исключая последнее значение i, для которого существует 1 итерация).

Итак, если T (n) - это время выполнения вашего исходного алгоритма тогда

T (2n) = 2 × T (n) + C × n

Что эквивалентно

T (n) = 2 × T (n / 2) + C × n / 2

, который распознается как типичная сложность двоичного разделения и завоевания O (n lg n) .