Рубрики

Алгоритмы | Анализ алгоритмов | Вопрос 8

Какова временная сложность функции ниже?

void fun(int n, int arr[])

{

    int i = 0, j = 0;

    for(; i < n; ++i)

        while(j < n && arr[i] < arr[j])

            j++;

}

(A) O (n)
(B) O (n ^ 2)
(C) O (nlogn)
(D) O (n (logn) ^ 2)

Ответ: (А)
Объяснение: На первый взгляд сложность по времени, по-видимому, составляет O (n ^ 2) из-за двух циклов. Но, пожалуйста, обратите внимание, что переменная j не инициализируется для каждого значения переменной i . Итак, внутренний цикл выполняется не более n раз. Пожалуйста, обратите внимание на разницу между данной функцией и приведенной ниже функцией:

void fun(int n, int arr[])

{

    int i = 0, j = 0;

    for(; i < n; ++i)

    {

        j = 0;

        while(j < n && arr[i] < arr[j])

            j++;

    }

}

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

Алгоритмы | Анализ алгоритмов | Вопрос 8

0.00 (0%) 0 votes