Это для цикла O (1) или O (n)?

Question

Дан массив [] = {0,2,6, ..., 1000000} с любым размером и фрагментом кода:

for i = 0 to size 
    print array[0]

Это O (1), потому что он толькопечатает первый элемент или O (n), потому что печатает его n (размер) раз?

Answer 1

Это O (n).

Так как этот for цикл имеет значение от 0 до размер , то есть for равно O (n).А внутри for это print array[0], что составляет O (1).

Таким образом, весь сегмент становится O (n) x O (1), который также равен O (n).

Он печатает первый элемент для n раз , что приводит к O (n).

Например, представьте следующий простой код назначения:

for i = 0 to size
    a = array[0]

Он также получает первый элемент для n раз , и это, очевидно, O (n) (игнорировать любую оптимизацию компилятора).

Answer 2

Это O (n), где n - размер заданного массива.

Скажем так: печать элемента массива занимает 1 секунду.

Если в массиве 1 элемент, программа напечатает первый элемент 1 раз, поэтому запуск программы занимает 1 секунду.

Если в массиве 10 элементов, программа напечатаетпервый элемент 10 раз, поэтому запуск программы занимает 10 секунд.

Если массив содержит 100 элементов, программа напечатает первый элемент 100 раз, поэтому запуск программы занимает 100 секунд.

Время, необходимое для запуска программы, увеличивается линейно с размером массива.Следовательно, алгоритм O (n).