Як визначити найгірший час виконання кожної програми за допомогою нотації big-O? [дублювати] - алгоритм, час виконання, дискретно-математика

У мене виникають проблеми з розумінням цього питання і як дійти до відповіді. Як ти розрахувати найгірший час запуску?

Вхід наступних програм - це масив A, що містить n цілих чисел A [1] · · · A [n]. Обмежте найгірший час виконання кожної програми за допомогою позначення big-O.

Проблема 1:

i = 1, total = 0
while i < n/2:
total = total + A[i]
i=i*2

Проблема 2:

total = 0
S = the set {1,2,3,4...n}
for each subset T of S
for each element x in T
total = total + A[x]

Проблема 3:

int i = 1, j = 1;
for i = 1 to n:
while (j < n && A[i] < A[j])
j++

Префіксальна сума масиву чисел A [1],. . . , A [n] - другий масив B [1],. . . , B [n] де

B [i] = підсумовування від j = 1 до i A [j]

Наступні проблеми обчислюють префіксну суму:

Проблема 4:

for i = 1 to n:
B[i] = 0;
for j = 1 to i:
B[i] += A[j]

Проблема 5:

B[1] = A[1];
for i = 2 to n:
B[i] = B[i-1] + A[i]

Відповіді:

1 для відповіді № 1

Проблема 1:
Алгоритм виконує постійну часову операцію (додавання) в точці кожного доступу, і цей доступ робиться при цьому i<n/2. З тих пір i подвоюється кожен раз, умова перестане тривати після log(n/4) кроки, тому найгірший час є складністю O (log (n)) (логарифмічний).

Проблема 2:
Алгоритм отримує доступ до кожного елемента масиву (x у псевдокоді) стільки разів, скільки в підмножині S, і виконує операцію постійного часу в точці доступу. Кожен елемент є в 2 ^ (n-1) підмножини, які містять себе, і є н таких елементів, тому найгірший час є складністю O (n * 2 ^ (n)) (експоненціальна).

Проблема 3:
Зауважте, що кожного разу, коли перевіряється умова в циклі, значення, значення i+j збільшується на 1і значення i+j ніколи не може зменшитися. З тих пір i+j починається з 2 і ніколи не може пройти повз 2n+1, загальна складність алгоритму становить O (n) (лінійний).

Проблема 4:
Для заданого значення i, працює внутрішня петля i разів. Далі, i коливається від 1 до n, тому ми виконуємо 1 + 2 + 3 + ... + n = n (n + 1) / 2 обчислення постійного часу (доповнення), тому загальна складність алгоритму становить O (n ^ 2) (квадратичний).

Проблема 5:
Алгоритм має доступ н-1 елементів масиву, і виконує постійну операцію в часі в точці кожного доступу (додавання), тому найгірша складність часу становить O (n) (лінійний).

---