сложность / время выполнения псевдокода с использованием нотации big-O

Question

Мне нужно немного помочь с проблемой. Я только начал читать о O-нотации, но я все еще новичок, когда дело доходит до анализа кода.

Так вот в чем проблема:

Дается следующий псевдокод, где A - числовое поле, элементы которого могут быть доступны через индексы от 1 до длины (A). я состоит из целых чисел, поэтому результаты деления округляются в меньшую сторону. В чем сложность функции SkipPrint?

1: procedure SkipPrint(A)
2:      i <- length(A)
3:          do
4:             print(A[i])
5:                 i <- i/2
6:                   while i>0

Так что я думаю, что сложность O (n), поскольку функция должна пройти через массив, но только один раз, верно? (строка 2) Каждая вторая строка имеет меньшую величину, поэтому она остается O (n)?

Спасибо заранее. Ваша помощь приветствуется.

Salute

Answer 1

Скажем, n = length(A) и предположим сначала, что мы находимся в более простом случае, где length(A) = 2^m, для некоторого целого числа m.

Тогда i, будучи разделенным пополам на каждом шаге, будет иметь значения:

2^m, 2^{m-1}, 2^{m-2}, ..., 2, 1, 0

, который показывает, что цикл будет выполняться m раз, пока i не достигнет 0. Поскольку n = 2^m, это означает, что m = lg n и, следовательно, сложность составляет O(lg n).

В общем случае определите m := floor(lg n). Приведенный выше анализ показывает, что цикл будет повторяться m раз, пока i не станет 0. Таким образом, сложность будет O(floor(lg n)), которая равна O(lg n).

Answer 2

Это будет O (n), да. Ты прав. Это потому, что существует один цикл, который повторяется в одном направлении. (i всегда становится меньше в этом случае)