Как я могу узнать большую букву O каждого из этих алгоритмов?

Question

У меня возникла проблема, когда у меня есть ряд вопросов, касающихся этих двух алгоритмов, однако я изо всех сил пытаюсь понять концепцию записи больших О, которая, как мне кажется, очень проста.

По сути, мне нужно выяснить, что такое большая буква O, сколько времени потребуется каждому алгоритму для решения проблемы одного и двух миллионов операций.

Алгоритм A:

SET sum TO 0
FOR i=1 to size
   FOR j=1 to 10000
   sum=sum+1

Алгоритм B:

SET sum TO 0
FOR i=1 to size
    FOR j=1 to size
    sum = sum + 1

Предполагается, что компьютер может выполнять миллион операций в секунду

Answer 1

Начиная с последней фразы вашего поста: временная сложность алгоритма не зависит от количества операций, которые компьютер может выполнять в секунду.Это не имеет значения.

Я полагаю, что оператор sum = sum + 1 принадлежит внутри внутреннего цикла FOR - отступ не делает это ясным.

Оба алгоритма выполняютсяsum = sum + 1 несколько раз.Мы можем считать, что одно выполнение sum = sum + 1 занимает постоянное время.

Теперь разница между этими двумя алгоритмами заключается в количестве выполнений внутреннего цикла.В первой версии это константа (10000).Это означает, что одно выполнение полного цикла FOR займет постоянное время.Это не зависит от size .

Это означает, что первый алгоритм имеет только один цикл, который зависит от size : он выполняет внутренний цикл size раз.И поэтому сложность времени составляет O (размер) .

Во второй версии, однако, внутренний цикл также выполняется размер раз.Так что это явно зависит от размера .Количество выполнений самого внутреннего оператора теперь составляет размер ² .Таким образом, сложность времени составляет O (размер ² ) .