Sprawdź się
#
? Przyprostokątne trójkąta składają się z znaków, przy czym o wartości 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 znaków, przy czym o wartości 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ą
#
? Przyprostokątne trójkąta składają się z znaków, przy czym o wartości 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ą.Funkcja , 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ć: . 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
Jaką złożoność czasową ma algorytm wyszukiwania największej spośród 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ą
Niech funkcja , 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ć: . Ile czasu zajmie realizacja tego algorytmu w sytuacji, gdy ? Przyjmij, że komputer wykonuje operacji w ciągu sekundy.
- około 27 godzin
- około 27 dni
- około 27 minut
- około 27 lat
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ą
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.
wynik ← wynik + i
, 2. Dopóki i <= (n⋅n) wykonuj:
, 3. i ← i + 1
, 4. i ← 1, wynik ← 0