Является ли временная сложность этой функции O (n * (n * log n²)) - PullRequest
1 голос
/ 26 сентября 2019

Что такое временная сложность функции ниже?n> 0

Function fun(n){
    Let count = 0;

    For( I = 0; I < n; I++){

        For(j = 0; j < n; j /= 2) {

            For(h = 0; h < n; h /= 2) {

                Count = count + 1;
            }
        }
    }
    Return count;
}

У меня есть O (n * (n * log n²)), но что-то подсказывает мне, что я могу ошибаться.

1 Ответ

2 голосов
/ 26 сентября 2019

Вышеуказанный цикл является бесконечным циклом.временная сложность для этого не может быть определена, если постановка задачи не обновлена ​​должным образом!

Function fun(n){
    Let count = 0;

    For( I = 0; I < n; I++){
        // will run infinitely even if you change j /= 2 to j *= 2, because initial value is 0
        For(j = 0; j < n; j /= 2) {
            // will run infinitely even if you change h /= 2 to h *= 2, because initial value is 0
            For(h = 0; h < n; h /= 2) {

                Count = count + 1;
            }
        }
    }
    Return count;
}
...