Примеры анализа Big-O

Опубликовано: 16 Декабря, 2021

Предпосылка: Анализ алгоритмов | Анализ Big-O

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

Существуют различные асимптотические обозначения, в которых измеряются временные сложности алгоритмов. Здесь обозначение «O» (Big O) используется для определения сложности времени. Сложность времени оценивает время выполнения алгоритма. Он рассчитывается путем подсчета элементарных операций. Всегда полезно знать причину времени выполнения так, чтобы она зависела только от алгоритма и его входных данных. Этого можно достичь, выбрав элементарную операцию, которую алгоритм выполняет многократно, и определив временную сложность T (N) как количество таких операций, которые алгоритм выполняет для массива длины N.

Пример 1 :

Временная сложность цикла с элементарными операциями : предполагается, что выполнение этих операций занимает единицу времени. Эту единицу времени можно обозначить O (1) . Если цикл выполняется N раз без какого-либо сравнения. Ниже приведена иллюстрация того же:

Выход:

 40 160

Пояснение: Временная сложность здесь будет O (N + M) . Первый цикл - это одиночный цикл for, который выполняется N раз, а вычисления внутри него занимают время O (1) . Точно так же другой цикл занимает M раз , объединяя оба разных цикла, добавляя их.
равно O (N + M + 1) = O (N + M) .

Пример 2 :

После ознакомления с элементарными операциями и одиночным циклом. Теперь, чтобы найти временную сложность для вложенных циклов, предположим, что это два цикла с разным количеством итераций. Можно видеть, что если внешний цикл выполняется один раз, внутренний будет выполняться M раз , давая нам последовательность как M + M + M + M + M ……… .N раз , это можно записать как N * M. Ниже приведена иллюстрация того же:

C ++

 // C++ program to illustrate time
 // complexity for nested loop
 #include <bits/stdc++.h>
 using namespace std;
 // Driver Code
 int main()
 {
    int a = 0, b = 0;
    int N = 4, M = 5; 
    // Nested loops
    for ( int i = 0; i < N; i++) {
        for ( int j = 0; j < M; j++) {
            a = a + j;
            // Print the current
            // value of a
            cout << a << ' ' ;
        }
        cout << endl;
    }
    return 0;
 }

Выход:

 0 1 3 6 10 
10 11 13 16 20 
20 21 23 26 30 
30 31 33 36 40

Пример 3 :

После получения вышеуказанных проблем. У нас есть два итератора, в которых внешний выполняется N / 2 раз, и мы знаем, что временная сложность цикла рассматривается как O (log N) , если итератор делится / умножается на постоянную величину K, тогда временная сложность рассматривается как O (log _K N) . Ниже приведена иллюстрация того же:

C ++

 // C++ program to illustrate time
 // complexity of the form O(log2 N)
 #include <bits/stdc++.h>
 using namespace std;
 // Driver Code
 int main()
 {
    int N = 8, k = 0; 
    // First loop run N/2 times
    for ( int i = N / 2; i <= N; i++) { 
        // Inner loop run log N
        // times for all i
        for ( int j = 2; j <= N;
             j = j * 2) {
            // Print the value k
            cout << k << ' ' ; 
            k = k + N / 2;
        }
    }
    return 0;
 }

Выход:

 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56

Пример 4 :

Теперь давайте разберемся с циклом while и попробуем обновить итератор как выражение. Ниже приведена иллюстрация того же:

C ++

 // C++ program to illustrate time
 // complexity while updating the
 // iteration
 #include <bits/stdc++.h>
 using namespace std;
 // Driver Code
 int main()
 {
    int N = 18;
    int i = N, a = 0; 
    // Iterate until i is greater
    // than 0
    while (i > 0) { 
        // Print the value of a
        cout << a << ' ' ;
        a = a + i;
        // Update i
        i = i / 2;
    }
    return 0;
 }

Выход:

 0 18 27 31 33

Пояснение: Уравнение для приведенного выше кода может быть представлено как:

=> (N/2)^K = 1 (for k iterations)
=> N = 2^k (taking log on both sides)
=> k = log(N) base 2.
Therefore, the time complexity will be
T(N) = O(log N)

Пример 5 : Другой способ определения временной сложности - преобразовать их в выражение и использовать следующее для получения требуемого результата. Учитывая выражение, основанное на алгоритме, задача состоит в том, чтобы решить и найти временную сложность. Эта методология проще, поскольку в ней используются базовые математические вычисления для расширения данной формулы для получения конкретного решения. Ниже приведены два примера для понимания метода.

Шаги:

Найдите решение для (N - 1) ^-й итерации / шага.
Аналогичным образом рассчитайте следующий шаг.
Как только вы познакомитесь с паттерном, найдите решение для K- ^го шага.
Найдите решение N раз и решите полученное выражение.

Ниже приведена иллюстрация того же:

Let the expression be:
T(N) = 3*T(N – 1).
T(N) = 3*(3T(N-2))
T(N) = 3*3*(3T(N – 3))
For k times:
T(N) = (3^k – 1)*(3T(N – k))

For N times:
T(N) = 3^N – 1 (3T(N – N))
T(N) = 3^N – 1 *3(T(0))
T(N) = 3^N * 1
T(N) = 3^N

Третий и самый простой метод - использовать теорему Мастера или вычислить временные сложности. Чтобы найти временную сложность с помощью теоремы Мастера , обратитесь к этой статье.

Статьи

Примеры анализа Big-O

C ++

C ++

C ++

РЕКОМЕНДУЕМЫЕ СТАТЬИ