Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 07. 06. 2015 19:00
Jak na složitosti algoritmů?
Ahoj mám takový problém stále nemůžu pochopit jak se počítají složitosti algoritmů. Základní pravidlo znám, když jsou cykly vnořené násobí se, když jsou cykly pod sebou tak se sčítají.
Cyklus for má složitost O(n), while ... o (log n)
Tohle všechno vím, ale nevím si rady, když mám více cyklů a podle různých iterací nevím jak poznat složitost.
Děkuji
Offline
#2 26. 08. 2015 01:35
- vulkan66
- Místo: Praha
- Příspěvky: 416
- Škola: ČVUT FJFI - Částicová fyzika
- Pozice: student
- Reputace: 20
Re: Jak na složitosti algoritmů?
↑ Matiniela:
Ahoj, asi trochu pozdě, ale i tak odpovím. Cyklus for je v podstatě totožný s while, takže nechápu proč by měli mít jinou složitost.
V následujícím příkladu je složitost O(N) (počet průchodů cyklem je N)
Code:
for (int i = 0; i < N; i++) "příkazy" = int i = 0 while(i < N) "příkazy" i++
Vím, jak ovládat vesmír. Tak mi řekněte, proč bych se měl hnát za milionem? -Grigorij Perelman
Offline
#3 27. 08. 2015 21:42
- check_drummer
- Příspěvky: 4897
- Reputace: 105
Re: Jak na složitosti algoritmů?
↑ Matiniela:
Ahoj, kdo ti řekl, že while cyklus má složitost o(log n)? A co třeba cyklus "while (true) {..}" Je to právě while cyklus, který činí informatiku netriviální.
"Máte úhel beta." "No to nemám."
Offline