← zpět

Úvod do časové složitosti

Co jsme dnes dělali

Tři algoritmy, tři rychlosti

Uvažme následující tři programy, které počítají stejnou věc: druhé mocniny čísel do nějakého čísla n.

n = int(input())

integers = []

for i in range(1, n):
    integers.append(i)

for j in range(1, n):
    if (j ** (1 / 2)) in integers:
        print(j, end=" ")

# 26
# 1 4 9 16 25

# 25
# 1 4 9 16
n = int(input())
i = 1
while i**2 < n:
    print(i**2, end=" ")
    i += 1
n = int(input())
for i in range(1, n):
    mocnina = i**2
    if mocnina < n:
        print(mocnina, end=" ")

Který z těchto algoritmů udělá nejvíce kroků (a je tedy nejpomalejší) a který nejméně (a je tedy nejrychlejší) v nejhorším případě (pro nejhorší vstupní hodnotu, pro nejhorší situaci)?

Snažíme se vyjádřit počet kroků jako funkci pomocí n, neboli kolik kroků algoritmus udělá pro vstupní hodnotu n.