алгоритм сложность псевдокода

Question

Это псевдокод для функции, которая превращает десятичные цифры в двоичные представления.

Вопрос: Покажите, что Ldiv2 [A] для n-значного числа - O (n). и определить, идущее сложность алгоритма

Входной представляет собой десятичное представление числа X, дают массивом цифр А [п-1], ...,

Следующий алгоритм использует «длинный деление на две "процедуры Ldiv2, которая делит десятичное число на 2. Алгоритм двоичного преобразования ниже преобразует массив десятичных цифр A [0..n-1] в массив бит B [0, ..4n-1] as следующим образом:

Initialize B[0, ..4n-1] array of bits, 
For i = 0 to 4n-1 do: 
    Begin 
    B[i]= A[0] %2; // % is the mod; 
    A = Ldiv2[A]; 
    End; 
Return B (possibly removing initial 0’s) 

Таким образом, для приведенного выше примера Х = 169, N = 2, в [0] = A [0]% 2 = 9% 2 = 1, то А = Ldiv2 [А] = 84, B [1] = A [0]% 2 = 4% 2 = 0 и т. Д.

для Ldiv2 [A] i положил это 4n-1 для n> 1, так что по определению должно быть O (n) , а для сложности выполнения алгоритма я полагаю, что это был O (n), потому что это только имеет один для цикла от 0 до 4n -1, хотя бит неясен, если для этого есть доказательство.

Answer 1

Мы запускаем в цикле 4n-1 раз и каждый раз заготовку выполняем действие, которое принимает в начале O(n) и O(1) в конце (когда A поворачивается на 1).

Таким образом, мы получаем:

(4n-1)*(n/log(n)) = O(n^2/log(n))