CSES - Aikavaativuudet

Ilmoita jokaisen algoritmin aikavaativuus. Oikea vastaus on aina jokin seuraavista: O(1), O(log n), O(n), O(n^2), O(n^3), O(n^4).

Kun painat lähetysnappia, vastauksesi tarkastetaan ja voit tarvittaessa korjata vastausta. Kun kaikki vastaukset ovat oikein, saat pisteen tehtävästä.

Algoritmi 1

for i = 1 to n
    for j = 1 to n
        for k = 1 to n
           ...

Aikavaativuus:

Algoritmi 2

for i = 1 to n
    ...
for i = 1 to 2*n
    ...
for i = 1 to 3*n
    ...

Aikavaativuus:

Algoritmi 3

for i = 1 to n*n
    for j = 1 to n*n
        ...

Aikavaativuus:

Algoritmi 4

k = n
while k > 0
    k -= 2

Aikavaativuus:

Algoritmi 5

k = 1
while k < 2*n
    k *= 2

Aikavaativuus:

Algoritmi 6

k = n
for i = 1 to n
    while k > 0
        k -= 1

Aikavaativuus:

Algoritmi 7

for i = 1 to 100
    for j = 1 to 10
       ...

Aikavaativuus:

Algoritmi 8

for i = 1 to n
    for j = 1 to n
        if i%2 == j%2
            break

Aikavaativuus:

Tietorakenteet ja algoritmit kevät 2023

Aikavaativuudet

Viikko 2