Вложенный l oop временная сложность (big-O) для алгоритма - PullRequest
0 голосов
/ 12 июля 2020

Я создал простую программу, и теперь мне нужно найти временную сложность (big-O). Ниже приведен код:

if(B <= A) {
    ...
    for(int i = 0; i < A; i++) {
        ...
    }
    
    for(int i = 0; i < B; i++) {
        ...
        if(input >= 1)
            validate = true;
        else
            validate = false;


    for(int i = 0; i < B; i++) {
        ...
        for(int k = i+1; k < B; k++) {
            ...
        }
    }
    
    if(validate == true) {
        ...
        for(int i = 0; i < B; i++)
            ...
    }
    else {
        ...
    }
}
else {
    ...
}

Это моя попытка решить проблему:

'if' can either be 0 or 1, therefore assigned 'z'
1st 'for loop' is A
2nd 'for loop' is B
'if' inside the 2nd 'for loop' is B, since it will run n time depending on the 2nd for loop
3rd 'for loop' is B
4th 'for loop' is B, since it is nested for loop inside 3rd 'for loop'
'if' can either be 0 or 1, therefore assigned 'v'
5th 'for loop' is B

Следовательно:

z + A + B + B + (B x B) + v + B
= z + A + 3B + B^2 + v
= O(B^2)

Я не понимаю, как рассчитать время сложность, когда задействованы вложенные циклы (я новичок в алгоритме). Мой подход частично верен или полностью неверен? Как мне подойти к такой проблеме временной сложности для такого простого алгоритма? расчет сложности тогда?

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...