Временная сложность цикла с вложенным if-else - PullRequest
Новая
       52

Временная сложность цикла с вложенным if-else

0 голосов
/ 12 октября 2018 
// Every iteration of loop counts triplet with 
// first element as arr[i]. 
for (int i = 0; i < n - 2; i++) { 

    // Initialize other two elements as corner 
    // elements of subarray arr[j+1..k] 
    int j = i + 1, k = n - 1; 

    // Use Meet in the Middle concept 
    while (j < k) { 

        // If sum of current triplet is more or equal, 
        // move right corner to look for smaller values 
        if (arr[i] + arr[j] + arr[k] >= sum) 
            k--; 

        // Else move left corner 
        else { 

            // This is important. For current i and j, 
            // there are total k-j third elements. 
            for (int x = j + 1; x <= k; x++) 
                cout << arr[i] << ", " << arr[j] 
                     << ", " << arr[x] << endl; 
            j++; 
        } 
    } 
}

Какова временная сложность этого алгоритма?Это O (n * n) ??Это проблема с веб-страницы geekforgeeeks.Как вы обрабатываете цикл внутри оператора else?

1 Ответ

0 голосов
/ 12 октября 2018

Разбейте код на части и найдите время выполнения каждого.

Внешний цикл for - O (n).

Каждый раз, когда вызывается этот цикл, вызывается цикл while.Таким образом, вы умножите сложность двух циклов.

Чтобы выяснить время выполнения цикла while, вам нужно взглянуть на блоки if и else.Если блок if выполняется каждый раз, тогда цикл while будет иметь сложность O (n).Если часть else выполняется каждый раз, тогда цикл while будет иметь сложность O (n ^ 2).

Если мы рассматриваем наихудший случай, вы бы проигнорировали время выполнения блоков if.Таким образом, время выполнения цикла while равно O (n ^ 2), и оно вызывается n раз через внешний цикл for.

Таким образом, время выполнения всего этого должно быть O (n ^ 3).

...