Разные проблемы временной сложности

Опубликовано: 21 Сентября, 2022

Предварительное условие: асимптотические обозначения.

Сложность времени:
Временная сложность — это время, необходимое алгоритму, выраженное как функция размера проблемы. Его также можно определить как количество компьютерного времени, необходимого для завершения программы. Когда мы решаем проблему временной сложности, это определение помогает больше всего —
«Это количество операций, которые алгоритм выполняет для выполнения своей задачи с учетом размера входных данных».

Ниже приведены некоторые разные задачи временной сложности, которые всегда часто задают в различных типах викторин.

1. Какова временная сложность следующего кода –

C++




void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh

C



void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
Java



public static void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh
Python3



def function(n):
    i = 1
    s = 1
    while (s < n):
        s = s + i
        i+=1
     
# This code is contributed by Shubham Singh
C#



public static void function(int n)
{
    int i = 1, s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh
Javascript



<script>
function functionn(int n)
{
    var i = 1;
    var s = 1;
    while (s < n) {
        s = s + i;
        i++;
    }
}
 
// This code is contributed by Shubham Singh
</script>
 
 
Решение -
 Временная сложность = O(√n).
 
Объяснение -
 Мы можем определить термины «S» в соответствии с соотношением S i = S i-1 + i. Пусть k - общее количество итераций, выполненных программой.
 
я С
 1 1
 2 2
 3 2 + 2
 4 2 + 2 + 3
 … …
 к 2 + 2 + 3 + 4 + ……+ к
 
Когда S >= n, цикл остановится на k -й итерации,
 ⇒ S>=n ⇒ S=n
 ⇒ 2 + 2 + 3 + 4 + ……+ k = n
 ⇒ 1 + (к * (к + 1))/2 = п
 ⇒ к 2 = п
 к = √n
 Следовательно, временная сложность равна O(√n).
 
2. Какова временная сложность следующего кода:
 
Решение -
 Временная сложность = O(1) в лучшем случае и O(n) в худшем случае.
Объяснение -
 Эта программа содержит условие if и else. Следовательно, есть 2 возможности временной сложности. Если значение n меньше 5, то на выходе мы получим только GeeksforGeeks , и его временная сложность будет O(1).
 Но если n>=5, то будет выполняться цикл for, и временная сложность станет O(n), это считается наихудшим случаем, поскольку требует больше времени.
3. Какова временная сложность следующего кода:
C++



void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
 
// This code is contributed by Shubham Singh
C



void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
Java



public static void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
 
// This code is contributed by Shubham Singh
Python3



def fun(a, b):
     
    while (a != b):
        if (a > b):
            a = a - b
        else:
            b = b - a
             
# This code is contributed by Shubham Singh
C#



public static void fun(int a, int b)
{
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
}
 
// This code is contributed by Shubham Singh
 
 
Решение -
 Временная сложность = O(1) в лучшем случае и O(max(a, b)) в худшем случае.
 
Объяснение -
 Если значения a и b совпадают, то цикл while выполняться не будет. Следовательно, временная сложность будет O (1).
 Но если a!=b, то будет выполняться цикл while. Пусть а=16 и b=5;
 
нет. итераций а б
 1 16 5
 2 16-5=11 5
 3 11-5=6 5
 4 6-5=1 5
 5 1 5-1=4
 6 1 4-1=3
 7 1 3-1=2
 8 1 2-1=1
 
В этом случае цикл while выполняется 8 раз (a/2⇒16/2⇒8).
 Если a=5 и b=16, то цикл также будет выполнен 8 раз. Таким образом, мы можем сказать, что временная сложность равна O(max(a/2,b/2))⇒O(max(a, b)) , это считается наихудшим случаем, поскольку требует больше времени.
 
4. Какова временная сложность следующего кода:
 
Решение -
 Временная сложность = O(√n).
Объяснение -
 Пусть k будет нет. итерации цикла.
я я * я
 1 1
 2 2 2
 3 3 2
 4 4 2
 … …
 к к 2
⇒ Цикл остановится, когда i * i >=n, т.е. i*i=n
 ⇒ i*i=n ⇒ k 2 = n
 ⇒ k =√n
 Следовательно, временная сложность равна O(√n).
5. Какова временная сложность следующего кода:
C++



void fun(int n, int x)
{
    for (int i = 1; i < n; i = i * x) //or for(int i = n; i >=1; i = i / x)
        cout << "GeeksforGeeks";
}
 
//This code is contributed by Shubham Singh
C



void fun(int n, int x)
{
    for (int i = 1; i < n; i = i * x) //or for(int i = n; i >=1; i = i / x)
        print("GeeksforGeeks");
}
 
 
Решение -
 Временная сложность = O (log x n).
 
Объяснение -
 Пусть k будет нет. итерации цикла.
 
нет. этого я=я*х
 1 1*х=х
 2 х*х=х 2
 3 х 2 * х = х 3
 … …
 к х к-1 * х = х к
 
⇒ Цикл остановится, когда i>=n ⇒ x k = n
 ⇒ x k =n (Возьмите бревно с обеих сторон)
 ⇒ k=log x n
 ⇒ Следовательно, временная сложность равна O(log x n).
 
6. Какова временная сложность следующего кода:
 
C



void fun(int n)
{
    for (int i = 0; i < n / 2; i++)
        for (int j = 1; j + n / 2 <= n; j++)
            for (int k = 1; k <= n; k = k * 2)
                cout << "GeeksforGeeks";
}
 
 
Решение -
 Временная сложность = O(n 2 log 2 n).
 
Объяснение -
 Временная сложность 1 -го цикла for = O(n/2) ⇒ O(n).
 Временная сложность второго цикла for = O(n/ 2 ) ⇒ O(n).
 Временная сложность 3- го цикла for = O (log 2 n). (см. номер вопроса – 5)
 Следовательно, временная сложность функции станет O(n 2 log 2 n).
 
7. Какова временная сложность следующего кода:
 
C



void fun(int n)
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j = j + i)
            cout << "GeeksforGeeks";
}
 
 
Решение . Временная сложность = O(nlogn).
 
Объяснение -
 Временная сложность 1-го цикла for = O(n). 2- й цикл выполняется n/i раз для каждого значения i.
 Его временная сложность равна O(∑ n i=1 n/i) ⇒ O(logn).
 Следовательно, временная сложность функции = O(nlogn).
 
8. Какова временная сложность следующего кода:
 
Решение . Временная сложность = O(n 2 ).
Объяснение -
 Временная сложность 1-го цикла for = O(n/3) ⇒ O(n).
 Временная сложность второго цикла for = O(n/4) ⇒ O(n).
 Следовательно, временная сложность функции станет O(n 2 ) .
9. Какова временная сложность следующего кода:
Решение . Временная сложность = O (log 2 n).
Объяснение -
 На каждой итерации i становится вдвое (TC=O(logn)) и j становится вдвое (TC=O(logn)). Таким образом, временная сложность станет O (log 2 n).
 Мы можем преобразовать этот цикл while в цикл for.
 for(int i = 1; i < n; i = i * 2)
 for(int j=n; j > 0; j = j/2).
Временная сложность цикла for, описанного выше, также равна O (log 2 n).
10. Рассмотрим следующий C-код. Какое количество сравнений выполняется при выполнении цикла?
Решение -
 ceil(log 2 n)+1.
Объяснение -
 Пусть k будет нет. итерации цикла. После k -го шага значение j равно 2k. Следовательно, k=log 2 n. Здесь мы используем ceil log 2 n , потому что log 2 n может быть десятичным. Так как делаем еще одно сравнение для выхода из цикла.
 Итак, ответ ceil(log 2 n)+1.

            

                            

                    
                                    

                        

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