Рассчитайте точное время сложности - PullRequest
Новая
       16

Рассчитайте точное время сложности

0 голосов
/ 29 ноября 2018

У меня есть этот псевдокод, который сортирует очередь, используя другую очередь: 

1) Q2.enqueue(Q1.dequeue)
2) while Q1.size > 0 do
     2.1) next <- Q1.dequeue
     2.2) for i <- 1 to i<=Q2.size do
             2.2.1) if Q2.first < next then
                    2.2.1.1) Q2.enqueue(Q2.dequeue)
             2.2.2) else do
                    2.2.2.1) Q2.enqueue(next)
                    2.2.2.2) next <- Q2.dequeue
     2.3) Q2.enqueue(next)

И я хотел бы рассчитать точное количество операций, которые будут выполнены при запуске этого алгоритма.

Итак, я начинаю с 1) - это всего лишь 1, тогда цикл while будет идти n-1 раз, пока его 1+ n-1.

Тогда внутри цикла 2.1 будет выполняться строка 2.1, так что ее 1 затем внутрибудут выполнены операции цикла 2, а затем строка 2.3, являющаяся частью цикла while.Цикл for пойдет сначала 1 раз, затем 2 и до n-1, и каждый раз будет выполняться 2 операции, поэтому его пока

Это правильно?

...