Wróć do informacji o e-podręczniku Wydrukuj Pobierz materiał do PDF Pobierz materiał do EPUB Pobierz materiał do MOBI Zaloguj się, aby dodać do ulubionych Zaloguj się, aby skopiować i edytować materiał Zaloguj się, aby udostępnić materiał Zaloguj się, aby dodać całą stronę do teczki
1
Pokaż ćwiczenia:
1
Ćwiczenie 1
RRCWcheJKqmZx
Wskaż, jaką złożoność obliczeniową ma algorytm zastosowany w programie rysującym trójkąt prostokątny za pomocą znaków #? Przyprostokątne trójkąta składają się z n znaków, przy czym o wartości n decyduje użytkownik na samym początku działania programu. Poniżej znajduje się jego pseudokod:
wczytaj(n) 
i ← 1
Dopóki i mniejsze równe n wykonuj
j ← 1
Dopóki j mniejsze równe i wykonuj
wypisz("#")
j ← j + 1
wypisz("\n")
i ← i + 1
Możliwe odpowiedzi: 1. złożoność liniową, 2. złożoność stałą, 3. złożoność liniowo-logarytmiczną, 4. złożoność kwadratową
Richs4fF2odoB
Wskaż, jaką złożoność obliczeniową ma algorytm zastosowany w programie rysującym trójkąt prostokątny za pomocą znaków #? Przyprostokątne trójkąta składają się z n znaków, przy czym o wartości n decyduje użytkownik na samym początku działania programu. Poniżej znajduje się jego pseudokod:
wczytaj(n) 
i ← 1
Dopóki i mniejsze równe n wykonuj
j ← 1
Dopóki j mniejsze równe i wykonuj
wypisz("#")
j ← j + 1
wypisz("\n")
i ← i + 1
Możliwe odpowiedzi: 1. kwadratową złożoność czasową., 2. liniową złożoność czasową., 3. stałą złożoność czasową., 4. liniowo-logarytmiczną złożoność czasową.
1
Ćwiczenie 2
RfFKc87pVW39K
Funkcja f, opisująca liczbę operacji składających się na algorytm w zależności od ilości danych wejściowych, ma następującą postać: f(n) = n3 +2n2. Czy algorytm ten ma kwadratową złożoność czasową? Możliwe odpowiedzi: 1. tak, ma on kwadratową złożoność czasową, 2. nie, nie ma on kwadratowej złożoności czasowej
2
Ćwiczenie 3
Rx2RRLnZFbTcZ
Jaką złożoność obliczeniową ma algorytm wyszukiwania największej spośród n liczb całkowitych podanych na wejściu? Możliwe odpowiedzi: 1. złożoność liniową, 2. złożoność kwadratową, 3. złożoność logarytmiczną, 4. złożoność stałą
2
Ćwiczenie 4
RtKnU4YzXEBFd
Chcemy, aby program liczył następującą sumę: 1 + 2 + ... +(n2-1) +n2. O wartości n decyduje użytkownik na początku działania programu. Jesteśmy w stanie podać sumę obliczając elementy cząstkowe od 1 do n2 i po kolei dodawać do wyniku każdą z liczb. Takie rozwiązanie ma złożoność kwadratową. Czy istnieje algorytm o mniejszej złożoności obliczeniowej, pozwalający wykonać to samo zadanie? Możliwe odpowiedzi: 1. Tak, istnieje algorytm o stałej złożoności, 2. Nie, nie istnieje algorytm o mniejszej złożoności obliczeniowej, 3. Tak, istnieje algorytm o złożoności liniowej, 4. Tak, istnieje algorytm o złożoności logarytmicznej
2
Ćwiczenie 5
RMuoZd8e6VRAS
Niech funkcja f, opisująca liczbę operacji składających się na algorytm w zależności od ilości danych wejściowych, będzie następującej postaci: f(n) = n2. Ile czasu zajmie realizacja tego algorytmu w sytuacji, gdy n = 107? Przyjmij, że komputer wykonuje 109 operacji w ciągu 1 sekundy. Możliwe odpowiedzi: 1. Około 27 godzin, 2. Około 27 dni, 3. Około 27 minut, 4. Około 27 lat
3
Ćwiczenie 6
R1BTbmOqZ2jjV
Zaznacz wszystkie właściwości pasujące do algorytmów o złożoności kwadratowej. Możliwe odpowiedzi: 1. Działają szybko dla dużych ilości danych wejściowych, 2. Działają szybko dla małych ilości danych wejściowych, 3. Dla dużych ilości danych wejściowych są wykonywane szybciej niż algorytmy o złożoności liniowej, 4. Mają wielomianową złożoność obliczeniową
3
Ćwiczenie 7
R3yivXK6PPZan
Wstaw brakujące wyrażenia tak, aby treść poniższego tekstu była prawdziwa. Projektując algorytmy o kwadratowej złożoności czasowej, 1. dużych, 2. złożoność pamięciową, 3. małych, 4. nie powinniśmy się zastanawiać, 5. wolniej, 6. złożoność projektową, 7. szybciej, 8. powinniśmy się zastanowić, czy można je w pewien sposób zoptymalizować. Dla 1. dużych, 2. złożoność pamięciową, 3. małych, 4. nie powinniśmy się zastanawiać, 5. wolniej, 6. złożoność projektową, 7. szybciej, 8. powinniśmy się zastanowić ilości danych wejściowych działają one zdecydowanie 1. dużych, 2. złożoność pamięciową, 3. małych, 4. nie powinniśmy się zastanawiać, 5. wolniej, 6. złożoność projektową, 7. szybciej, 8. powinniśmy się zastanowić od algorytmów stałych czy liniowych. Należy również mieć na uwadze 1. dużych, 2. złożoność pamięciową, 3. małych, 4. nie powinniśmy się zastanawiać, 5. wolniej, 6. złożoność projektową, 7. szybciej, 8. powinniśmy się zastanowić algorytmów. Może się zdarzyć tak, że optymalizacja czasowa będzie możliwa dzięki zwiększeniu wykorzystywanej przez program pamięci komputerowej, co może nie być pożądane.
3
Ćwiczenie 8
RtNcL86tlYkae
Uporządkuj kolejne kroki pseudokodu algorytmu o kwadratowej złożoności czasowej, który jest wykorzystywany do obliczenia następującej sumy: 1 +2 + ...  + (n2-1) +n2 Elementy do uszeregowania: 1.     wynik ← wynik + i, 2. Dopóki i <= (n⋅n) wykonuj:, 3.     i ← i + 1, 4. i ← 1, wynik ← 0
Rf7E00fwYoLJK
Zastanów się, czy jest prostszy sposób (o mniejszej złożoności czasowej) na wyznaczenie tej sumy. Jeśli tak, podaj go. (Uzupełnij).