Рубрики

Интересный вопрос сложности времени

Какова временная сложность следующей функции fun ()?

int fun(int n)

{    

    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j < n; j += i)

        {

            // Некоторая задача O (1)

        }

    }    

}

Для i = 1 внутренний цикл выполняется n раз.
Для i = 2 внутренний цикл выполняется примерно n / 2 раза.
Для i = 3 внутренний цикл выполняется примерно n / 3 раза.
Для i = 4 внутренний цикл выполняется примерно n / 4 раза.
…………………………………………………….
…………………………………………………….
Для i = n внутренний цикл выполняется примерно n / n раз.

Таким образом, общая временная сложность приведенного выше алгоритма составляет (n + n / 2 + n / 3 +… + n / n)

Рекомендуемые посты:

Интересный вопрос сложности времени

0.00 (0%) 0 votes