время сложность некоторой рекурсивной и ни один рекурсивный алгоритм

Question

У меня есть два алгоритма псевдо-код:

RandomAlgorithm(modVec[0 to n − 1]) 
b = 0; 
for i = 1 to n do 
    b = 2.b + modVec[n − i]; 
for i = 1 to b do 
    modVec[i mod n] = modVec[(i + 1) mod n]; 
return modVec; 

Второе:

AnotherRecursiveAlgo(multiplyVec[1 to n]) 
if n ≤ 2 do 
    return multiplyVec[1] × multiplyVec[1]; 
return 
    multiplyVec[1] × multiplyVec[n] + 
    AnotherRecursiveAlgo(multiplyVec[1 to n/3]) + 
    AnotherRecursiveAlgo(multiplyVec[2n/3 to n]); 

Мне нужно анализировать временную сложность этих алгоритмов: Для первый алгоритм i получил первый цикл в O (n), второй цикл имеет наилучший случай и худший случай, наилучшим случаем является то, что O (1) цикл выполняется один раз, в худшем случае мы имеем большой n на первый цикл, но я не знаю, как написать эту идею как причину сложности времени, которую я обычно получаю b = сумма (от 1 до n-1) 2^n-1. modVec [n-1] и я застрял здесь.

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

Спасибо за помощь.

Answer 1

Первая проблема немного странная, все в порядке. Если это поможет, представьте modVec как массив 1 и 0. В этом случае первый цикл преобразует этот массив в значение. Это О (п)

Например, (1, 1, 0, 1, 1) даст Ь = 27.

Ваш второй цикл выполняется б раз. Доминирующим термином для значения b является 2^(n-1), a.k.a. O (2^n). Назначение, которое вы выполняете внутри цикла, равно O (1).

---

Второй цикл делает зависит от п. Ваш базовый случай - простое умножение, O (1). Шаг рекурсии имеет три условия:

• простое умножение
• повторяются на п/3 элементов
• повторяются на п/3 элементов (от 2n/3 до конца равно п/3 элементы)

Точно так же, как ваши двоичные разделы приводят к log [2] сложностям, в результате этого будет log [3]. База не имеет значения; коэффициент (два рекурсивных вызова) не имеет значения. 2 * O (log3) все еще O (log N).

Это подталкивает вас к решению?

Answer 2

Первый цикл

Для меня это сводится к O (First-For-Loop) + O (Second-For-Loop).

O (First-For-Loop) просто = O (n).

O (Second-for-Loop) интересно зависит от n. Поэтому для меня это можно представить как O (f (n)), где f (n) - некоторая функция от n. Не совсем уверен, если я понимаю f (n) на основе представленного кода.

Ответ, следовательно, становится O (n) + O (f (n)). Это может сводиться к O (n) или O (f (n)), в зависимости от того, какой из них больше и доминирует (поскольку члены более низкого порядка не имеют значения в обозначениях большого О.

Вторая петля

в этом случае, я вижу, что каждый вызов функции вызывает 3 дополнительных вызовов ...

Первый звонок, кажется, O (1) вызов. Так что это не будет иметь никакого значения.

Второй и третий вызовы, как представляется, возвращают функцию. Поэтому каждый вызов функции приводит к 2 дополнительных рекурсии.

Следовательно, временной сложностью на этом будет O (2^n).