2019-gate-computer-science-and-it-practice.pdf/Q21-alg3

Вопрос: Q21-alg3-31d68c

Какая временная сложность выполнения данного кода?

for (i = n; i > 0; i/= 2){
    for (int j = 1; j < n; j * = 2){
        for (int k = 0; k < n; k + = 2){
        sum + = (i + j * k);
        }
    }
}

Ответы

• Правильный ответ:

Объяснение

• Во внешнем цикле for переменная i уменьшается вдвое, поэтому она проходит цикл (log n) раз.
• Для каждого следующего цикла i также выполняется цикл (log n) раз из-за удвоения переменной j.
• Самый внутренний цикл на k выполняется n/2 раза.
• Циклы являются вложенными, поэтому границы должны быть умножены.
• В результате, получается значение алгоритма .

Исходники — вопрос 21 на 234 странице книги «2019-gate-computer-science-and-it-practice.pdf»

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.