Ako určiť najhoršom spustiť každý program pomocou big-O zápis?[kopírovať] - algoritmus, runtime, diskrétna matematika

Mám problém pochopiť túto otázku a ako sa dostať k odpovedi. Ako vy vypočítať najhorší čas spustenia?

Vstupom nasledujúcich programov je pole A obsahujúce celé čísla A [1] · · · A [n]. Väzba najhoršieho času spustenia každého programu pomocou zápisu veľkého písmena O.

Problém 1:

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

Problém 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]

Problém 3:

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

Prefixová súčet poľa čísel A [1],. , , , A [n] je druhé pole B [1],. , , , B [n] kde

B [i] = súčet z j = 1 až i A [j]

Nasledujúce problémy vypočítajú sumu predpony:

Problém 4:

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

Problém 5:

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

odpovede:

1 pre odpoveď č. 1

Problém 1:
Algoritmus uskutočňuje konštantnú časovú operáciu (prírastok) v bode každého prístupu a prístup sa uskutočňuje v čase i<n/2, od tej doby i zdvojnásobí sa, stav sa už nebude ďalej držať log(n/4) krokov, takže najhoršia časová zložitosť je O (log (n)) (logaritmická).

Problém 2:
Algoritmus pristupuje ku každému prvku poľa (x v pseudokóde) toľkokrát, koľko je v podskupine S, a vykonáva konštantnú časovú operáciu v mieste prístupu. Každý prvok je v 2 ^ (n-1) podmnožiny, ktoré obsahujú samy seba a existujú n takýchto prvkov, takže najhoršia časová zložitosť je O (n * 2 ^ (n)) (exponenciálne).

Problém 3:
Všimnite si, že vždy keď je zaškrtnutá podmienka v okruhu while, hodnota i+j zvyšuje sa o 1a hodnota i+j nemôže nikdy klesnúť. od tej doby i+j začína o 2 a nikdy nemôže prekonať 2n+1, celková zložitosť algoritmu je O (n) (lineárne).

Problém 4:
Pre danú hodnotu i, vnútorná slučka beží i časy. ďalej i sa pohybuje v rozmedzí od 1 do n, takže vykonávame 1 + 2 + 3 + ... + n = n (n + 1) / 2 konštantné výpočty (dodatky), takže celková zložitosť algoritmu je O (n ^ 2) (kvadratická).

Problém 5:
Prístup k algoritmu n-1 prvky poľa a vykonáva konštantnú časovú operáciu v bode každého prístupu (prídavok), takže najhoršia časová zložitosť je O (n) (lineárne).

---