сложность функций в C - PullRequest
Новая
       7

сложность функций в C

0 голосов
/ 20 февраля 2019 
int f1(int N) {
    int Sum, i, j, k;
    Sum = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < i * i; j++)
            for (k = 0; k < j; k++)    
                Sum++;
    return Sum;
}

int f2(int N) {
    int Sum, i, j;
    Sum = 0;
    for (i = 0; i < 10; i++)
        for (j = 0; j < i; j++)
            Sum += j * N;
    return Sum;
}

Каковы сложности f1 и f2?

Я понятия не имею о сложности f1, и я думаю, что сложность f2 должна быть O (1) , поскольку число итераций постоянно.Это правильно?

Ответы [ 3 ]

0 голосов
/ 20 февраля 2019

Сложность f1 в O (n ^ 5), поскольку 

for(i=0; i<N; i++) //i has a upper bound of n 
    for(j=0; j<i*i; j++) //j has a upper bound of i^2, which itself has the upper bound of n, so this is n^2
        for(k=0; k<j; k++) //k has a upper bound of j, which is n^2  
            Sum++; //constant

Таким образом, полная верхняя граница равна n * n ^ 2 * n ^ 2, что равно n ^ 5, поэтому f1 находится в O (n ^ 5). 

for (i = 0; i < 10; i++) //upper bound of 10 so in O(10) which is in O(1)
    for (j = 0; j < i; j++) //upper bound of i so also O(1)
        Sum += j * N; //N is just a integer here, and multiplication is a constant operation independent of the size of N, so also O(1)

Так что f2 находится в O (1 * 1 * 1), что является просто O (1).Обратите внимание, что все присваивания и объявления также являются постоянными.

Кстати, поскольку Sum++ не имеет побочных эффектов и с соответствующими циклами разрабатывает серию, для которой мы знаем решение (математика, программист или оптимальный оптимизатор компилятора, которое может уменьшитьf1 для постоянной программы, использующей формулу суммы гауссовских чисел (n*n+n) / 2, поэтому сумма может быть просто вычислена как-то вроде (N*N + N ) / 2 * (N*N*N*N + N*N) / 2) * 2, однако моя формула не учитывает начало с 0.

0 голосов
/ 20 февраля 2019

Использование сигма-нотации :

f1:

Внешний цикл работает от 0 до N, внутренний цикл - от 0 доi ^ 2, а последний выполняется от 0 до j, и внутри у нас есть только одна операция, поэтому мы суммируем 1. Таким образом, мы получаем:

1

1 + 1 + 1 ... j раз дает 1 * j = j, таким образом, мы получаем:

3

Используя правило сумма натуральных чисел , но мы заменяем n (в статье в Википедии) на i ^ 2, поэтому получаем:

4

Причина приближения заключается в том, что при определении временной сложности функции и сложения нескольких степеней мы берем наибольшую.Это просто делает математику проще.Например, f(n)=(n^3+n^2+n)=O(n^3) (предполагая, что f (n) представляет максимальное время работы, требуемое данным алгоритмом в зависимости от размера ввода n).

И используя формулу для суммирования первых Nчисла до 4-й степени, которые мы получаем (посмотрите на примечание в конце):

6

Таким образом, сложность времени для f1 составляет O(n^5).

f2:

Используя тот же метод, мы получаем:

2

8

Но это просто дает константу, которая не зависит от n, поэтому временная сложность для f2 равна O(1).

note:

Когда мы имеем суммированиепервые N чисел, которые относятся к степени K, сложность по времени будет N ^ (K + 1), поэтому вам, очевидно, не нужно запоминать формулу.Например:

9

0 голосов
/ 20 февраля 2019

Ваша первая функция имеет сложность O (N ^ (1 + 2 + 2)) = O (N ^ 5).

В первом цикле я переходит от 0 к N, вторая jзацикливается на пределе, зависящем от N ^ 2, а в третьем - k зацикливается на интервале, размер которого также зависит от N ^ 2.

Функция F2 имеет постоянное время, поэтому O (1) потому чтоциклы не имеют какой-либо степени свободы.

Этот тип материала изучается в курсах алгоритмов по теме "сложность".

Существует также другой тип измерения сложности алгоритмов.на основе омега-нотации .

...