Блог

Главная - Вопросы по программированию - Какова сложность выполнения этого алгоритма? это O(n)?

Какова сложность выполнения этого алгоритма? это O(n)?

#big-o

Вопрос:

Я просто хочу знать, является ли этот алгоритм O(n).

 for(int i=0;i<n;i  ){
    if(a[i]==0){
        temp=a[i];
        i  ;
        while(a[i]!=0){
            a[i]=temp;
            i  ;
        }
        i--;
    }
}

Комментарии:

1. Алгоритм увеличивается i без привязки во внутреннем цикле. Это может привести к выходу за пределы массива, что недопустимо.

2. Чего пытается достичь этот код?

3. пожалуйста, не забудьте выбрать лучший ответ

Ответ №1:

Да, это O(n). Если все значения in a не кратны 10, это обычный цикл for. Если while цикл введен, любые итерации в while цикле пропускаются в for цикле, что означает, что они не требуют дополнительного времени. Так что да, это всегда будет O(n).

Тем не менее, я рекомендую не изменять вашу переменную итерации в другом месте, кроме for объявления. Это делает код трудным для понимания и подверженным ошибкам.

Метки: