Sprawdź się

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ą

Jaką złożoność czasową 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 <= n wykonuj
	j ← 1

	Dopóki j <= i wykonuj 
		wypisz("#")
		j ← j + 1

	wypisz("\n")
	i ← i + 1

  • liniową złożoność czasową
  • stałą złożoność czasową
  • liniowo-logarytmiczną złożoność czasową
  • kwadratową złożoność czasową
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

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ą?

  • tak, ma on kwadratową złożoność czasową
  • 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łą

Jaką złożoność czasową ma algorytm wyszukiwania największej spośród n liczb całkowitych podanych na wejściu? Poniżej znajduje się jego pseudokod: 

maksimum ← Liczby[1] 
i ← 2

Dopóki i <= n wykonuj
	Jeżeli maksimum < Liczby[i]
		maksimum ← Liczby[i]

	i ← i + 1

wypisz(maksimum)

  • liniową złożoność czasową
  • kwadratową złożoność czasową
  • logarytmiczną złożoność czasową
  • stałą złożoność czasową
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

Niech 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) = n2. Ile czasu zajmie realizacja tego algorytmu w sytuacji, gdy n = 107? Przyjmij, że komputer wykonuje 109 operacji w ciągu 1 sekundy.

  • około 27 godzin
  • około 27 dni
  • około 27 minut
  • 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ą

Zaznacz wszystkie właściwości pasujące do algorytmów o kwadratowej złożoności czasowej.

  • Są wykonywane szybko dla dużych ilości danych wejściowych
  • Są wykonywane szybko dla małych ilości danych wejściowych
  • Dla dużych ilości danych wejściowych są wykonywane szybciej niż algorytmy o liniowej złożoności czasowej
  • Mają wielomianową złożoność czasową
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.

Wstaw brakujące wyrażenia tak, aby treść poniższego tekstu była prawdziwa.

dużych, powinniśmy się zastanowić, małych, szybciej, złożoność projektową, złożoność pamięciową, nie powinniśmy się zastanawiać, wolniej

Projektując algorytmy o kwadratowej złożoności czasowej, .................................................................., czy można je w pewien sposób zoptymalizować. Dla .................................................................. ilości danych wejściowych działają one zdecydowanie .................................................................. od algorytmów stałych czy liniowych. Należy również mieć na uwadze .................................................................. 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).
Aplet
Dla nauczyciela