Рубрики

Анализ алгоритмов | Комплект 5 (Практические задачи)

Мы обсуждали асимптотический анализ , наихудшие, средние и наилучшие случаи , асимптотические обозначения и анализ циклов в предыдущих постах.

В этом посте обсуждаются практические задачи по анализу алгоритмов.

Задача 1: Найти сложность ниже повторения:

         { 3T(n-1), if n>0,
T(n) =   { 1, otherwise

Решение:

Let us solve using substitution.
T(n) = 3T(n-1)
     = 3(3T(n-2)) 
     = 32T(n-2)
     = 33T(n-3)
       ...
       ...
     = 3nT(n-n)
     = 3nT(0) 
     = 3n
This clearly shows that the complexity 
of this function is O(3n).

Задача 2: Найти сложность повторения:

        { 2T(n-1) - 1, if n>0,
T(n) =   { 1, otherwise

Решение:

 Let us try solving this function with substitution.
T(n) = 2T(n-1) - 1
     = 2(2T(n-2)-1)-1 
     = 22(T(n-2)) - 2 - 1
     = 22(2T(n-3)-1) - 2 - 1 
     = 23T(n-3) - 22 - 21 - 20
       .....
       .....
     = 2nT(n-n) - 2n-1 - 2n-2 - 2n-3
       ..... 22 - 21 - 20

     = 2n - 2n-1 - 2n-2 - 2n-3
       ..... 22 - 21 - 20
     = 2n - (2n-1) 
[Note: 2n-1 + 2n-2 + ...... +  20 = 2n ]
T(n) = 1
Time Complexity is O(1). Note that while 
the recurrence relation looks exponential
the solution to the recurrence relation 
here gives a different result.

Задача 3: Найти сложность приведенной ниже программы:

function(int n)

{

    if (n==1)

       return;

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

    {

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

        {

            printf("*");

            break;

        }

    }

}

Решение: рассмотрите комментарии в следующей функции.

function(int n)

{

    if (n==1)

       return;

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

    {

        // Внутренний цикл выполняет только один

        // время из-за оператора перерыва

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

        {

            printf("*");

            break;

        }

    }

}

Сложность времени вышеуказанной функции O (n). Хотя внутренний цикл ограничен n, но из-за оператора break он выполняется только один раз.

Задача 4: Найти сложность приведенной ниже программы:

void function(int n)

{

    int count = 0;

    for (int i=n/2; i<=n; i++)

        for (int j=1; j<=n; j = 2 * j)

            for (int k=1; k<=n; k = k * 2)

                count++;

}

Решение: рассмотрите комментарии в следующей функции.

void function(int n)

{

    int count = 0;

    for (int i=n/2; i<=n; i++)

  

        // Выполняет O (Log n) раз

        for (int j=1; j<=n; j = 2 * j)

  

            // Выполняет O (Log n) раз

            for (int k=1; k<=n; k = k * 2)

                count++;

}

Сложность времени вышеуказанной функции O (n log 2 n).

Задача 5: Найти сложность приведенной ниже программы:

void function(int n)

{

    int count = 0;

    for (int i=n/2; i<=n; i++)

        for (int j=1; j+n/2<=n; j = j++)

            for (int k=1; k<=n; k = k * 2)

                count++;

}

Решение: рассмотрите комментарии в следующей функции.

void function(int n)

{

    int count = 0;

  

    // внешний цикл выполняется n / 2 раза

    for (int i=n/2; i<=n; i++)

  

        // средний цикл выполняется n / 2 раза

        for (int j=1; j+n/2<=n; j = j++)

  

            // внутренний цикл выполняет время входа в систему

            for (int k=1; k<=n; k = k * 2)

                count++;

}

Сложность времени вышеуказанной функции O (n 2 logn).

Задача 6: Найти сложность приведенной ниже программы:

void function(int n)

{

    int i = 1, s =1;

    while (s <= n)

    {

        i++;

        s += i;

        printf("*");

    }

}

Решение: мы можем определить термины 's' согласно соотношению s i = s i-1 + i. Значение 'i' увеличивается на единицу для каждой итерации. Значение, содержащееся в 's' на i- й итерации, является суммой первых положительных целых чисел 'i'. Если k — это общее количество итераций, выполненных программой, то цикл while завершается, если: 1 + 2 + 3…. + K = [k (k + 1) / 2]> n So k = O (√n).

Сложность времени указанной функции O (√n).

Задача 7: Найти жесткую верхнюю границу сложности приведенной ниже программы:

void function(int n)

{

    int count = 0;

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

        for (int j=i; j< i*i; j++)

            if (j%i == 0)

            {

                for (int k=0; k<j; k++)

                    printf("*");

            }

}

Решение: рассмотрите комментарии в следующей функции.

void function(int n)

{

    int count = 0;

  

    // выполняется n раз

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

  

        // выполняет O (n * n) раз.

        for (int j=i; j< i*i; j++)

            if (j%i == 0)

            {

                // выполняет j раз = O (n * n) раз

                for (int k=0; k<j; k++)

                    printf("*");

            }

}

Сложность по времени вышеуказанной функции O (n 5 ).

Эта статья предоставлена г-ном Сомешем Авастхи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Анализ алгоритмов | Комплект 5 (Практические задачи)

0.00 (0%) 0 votes