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

31.12.2019Анализ

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

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

Задача 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)) 
     = 3²T(n-2)
     = 3³T(n-3)
       ...
       ...
     = 3ⁿT(n-n)
     = 3ⁿT(0) 
     = 3ⁿ
This clearly shows that the complexity 
of this function is O(3ⁿ).

Задача 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 
     = 2²(T(n-2)) - 2 - 1
     = 2²(2T(n-3)-1) - 2 - 1 
     = 2³T(n-3) - 2² - 2¹ - 2⁰
       .....
       .....
     = 2ⁿT(n-n) - 2^n-1 - 2^n-2 - 2^n-3
       ..... 2² - 2¹ - 2⁰

     = 2ⁿ - 2^n-1 - 2^n-2 - 2^n-3
       ..... 2² - 2¹ - 2⁰
     = 2ⁿ - (2ⁿ-1) 
[Note: 2^n-1 + 2^n-2 + ...... +  2⁰ = 2ⁿ ]
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 ² 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 ² 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 ⁵ ).

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

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

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

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

0.00 (0%) 0 votes