Implementacja algorytmu (wersja iteracyjna)
Implementacja algorytmu (wersja iteracyjna)
1. Algorytm znajduje rozwiązanie wykonując 2*(n‑1) porównań (I wersja)
Linia 1. def min podkreślnik max podkreślnik it otwórz nawias okrągły tablica zamknij nawias okrągły dwukropek.
Linia 2. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 3. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 5. for element in tablica otwórz nawias kwadratowy 1 dwukropek zamknij nawias kwadratowy dwukropek.
Linia 6. if element otwórz nawias ostrokątny minimum dwukropek.
Linia 7. minimum znak równości element.
Linia 8. if element zamknij nawias ostrokątny maksimum dwukropek.
Linia 9. maksimum znak równości element.
Linia 11. return minimum przecinek maksimum.
Linia 12. tablica znak równości otwórz nawias kwadratowy 1 przecinek 4 przecinek 5 przecinek 3 przecinek 7 przecinek 9 zamknij nawias kwadratowy.
Linia 13. print otwórz nawias okrągły min podkreślnik max podkreślnik it otwórz nawias okrągły tablica zamknij nawias okrągły zamknij nawias okrągły.
Jak działa program?
Zaczynamy od pierwszego elementu
Przechodzimy po liście raz
W każdej iteracji aktualizujemy minimum i maksimum
2. Algorytm znajduje rozwiązanie korzystając z efektywniejszego algorytmu min‑max (II wersja)
Linia 1. def min podkreślnik max podkreślnik iter podkreślnik dziel podkreślnik i podkreślnik zwyciezaj otwórz nawias okrągły tablica zamknij nawias okrągły dwukropek.
Linia 2. n znak równości len otwórz nawias okrągły tablica zamknij nawias okrągły.
Linia 4. kratka jeśli lista ma tylko jeden element.
Linia 5. if n znak równości znak równości 1 dwukropek.
Linia 6. return tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 8. kratka inicjalizacja.
Linia 9. if n procent 2 znak równości znak równości 0 dwukropek.
Linia 10. if tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy otwórz nawias ostrokątny tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy dwukropek.
Linia 11. minimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 12. maksimum znak równości tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy.
Linia 13. else dwukropek.
Linia 14. minimum znak równości tablica otwórz nawias kwadratowy 1 zamknij nawias kwadratowy.
Linia 15. maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 16. start znak równości 2.
Linia 17. else dwukropek.
Linia 18. minimum znak równości maksimum znak równości tablica otwórz nawias kwadratowy 0 zamknij nawias kwadratowy.
Linia 19. start znak równości 1.
Linia 21. kratka przeglądanie par.
Linia 22. for i in range otwórz nawias okrągły start przecinek n przecinek 2 zamknij nawias okrągły dwukropek.
Linia 23. if tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny tablica otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy dwukropek.
Linia 24. mniejszy znak równości tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 25. wiekszy znak równości tablica otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy.
Linia 26. else dwukropek.
Linia 27. mniejszy znak równości tablica otwórz nawias kwadratowy i plus 1 zamknij nawias kwadratowy.
Linia 28. wiekszy znak równości tablica otwórz nawias kwadratowy i zamknij nawias kwadratowy.
Linia 30. if mniejszy otwórz nawias ostrokątny minimum dwukropek.
Linia 31. minimum znak równości mniejszy.
Linia 32. if wiekszy zamknij nawias ostrokątny maksimum dwukropek.
Linia 33. maksimum znak równości wiekszy.
Linia 35. return minimum przecinek maksimum.
Porównanie obu wersji:
Zwykła wersja iteracyjna (I program): ~2 (n - 1) porównań
II wersja : ~3n/2 porównań ten sam wynik, mniej porównań