Úvod do časové složitosti

• Co jsme dnes dělali
  • Organizační záležitosti
  • Tři algoritmy, tři rychlosti
  • Braní většího vstupu

Co jsme dnes dělali

Organizační záležitosti

• Přecházíme na ReCodEx, Coding Classroom používat přestáváme
  • Po odevzdání zkontrolujeme, jestli prochází testy. Pokud ne, zkoušíme opravit (podle výstupů) nebo zažádáme o revizi.
  • Pokud vše prochází, zažádáme o revizi. Úkol se považuje za odevzdaný, až vám řešení vrátím zpět bez komentářů vyžadující řešení.
• (možná stihneme) GitLab
  • Nastavili jsme si PAT, kterým jsme se přihlásili.
  • Použili jsme příkaz git clone ..., abychom si repozitář naklonovali k sobě na počítač.
  • Používáme VS Code pro správu repozitáře (staging, commit, push)
  • Doma prosím nastavte to samé

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.

Braní většího vstupu