Wskaż, jaką złożoność obliczeniową ma algorytm wyszukiwania binarnego. Możliwe odpowiedzi: 1. Złożoność liniową., 2. Złożoność logarytmiczną., 3. Złożoność liniowo-logarytmiczną., 4. Złożoność kwadratową.
1
Ćwiczenie 2
R1afYWArZ1rZI
Wskaż poprawną definicję algorytmu rekurencyjnego. Możliwe odpowiedzi: 1. Algorytm który rozwiązując dany problem wywołuje sam siebie (jeden lub więcej razy), 2. Algorytm który rozwiązując dany problem wywołuje inne algorytmy (jeden lub więcej razy), 3. Algorytm który rozwiązując dany problem generuje wszystkie możliwe odpowiedzi, a następnie sprawdza, które z nich są poprawne, 4. Algorytm który rozwiązując dany problem korzysta z podstawowych struktur danych
1
Ćwiczenie 3
R13ECXgZ9rtPL
Wskaż, jaką złożoność obliczeniową ma algorytm sortowania przez scalanie. Możliwe odpowiedzi: 1. Złożoność liniową., 2. Złożoność kwadratową., 3. Złożoność logarytmiczną., 4. Złożoność liniowo-logarytmiczną.
2
Ćwiczenie 4
R19FSFt6WteAr
Wskaż, ile czasu będzie wykonywany ten algorytm w sytuacji, gdy ? Niech funkcja , opisująca liczbę operacji składających się na algorytm w zależności od ilości danych wejściowych, ma postać: . Przyjmij, że komputer wykonuje operacji w ciągu sekundy. Możliwe odpowiedzi: 1. Około sekund., 2. Około minut., 3. Około godzin., 4. Około dni.
2
Ćwiczenie 5
R149X7IkYOYeF
Wskaż, czy algorytm ten ma złożoność logarytmiczną, wiedząc, że 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ć: . Możliwe odpowiedzi: 1. Nie, nie ma on złożoności logarytmicznej., 2. Tak, ma on złożoność logarytmiczną.
2
Ćwiczenie 6
R1HDRleQPGHDu
Wstaw brakujące wyrażenia tak, aby treść poniższego tekstu była prawdziwa. Algorytmy o złożoności logarytmicznej i liniowo-logarytmicznej bardzo często korzystają z metody 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj". Polega ona na podziale głównego problemu na mniejsze 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj". Algorytmy o złożoności liniowo-logarytmicznej są wykonywane szybciej od 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj", ale za to wolniej od 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj".
Wstaw brakujące wyrażenia tak, aby treść poniższego tekstu była prawdziwa. Algorytmy o złożoności logarytmicznej i liniowo-logarytmicznej bardzo często korzystają z metody 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj". Polega ona na podziale głównego problemu na mniejsze 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj". Algorytmy o złożoności liniowo-logarytmicznej są wykonywane szybciej od 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj", ale za to wolniej od 1. „łącz i zwyciężaj", 2. liniowych, 3. nadproblemy, 4. podproblemy, 5. kwadratowych, 6. „dziel i zwyciężaj".
3
Ćwiczenie 7
RqB3pxL4gdBBP
Uporządkuj poniższe złożoności obliczeniowe od najszybszej do najwolniejszej dla dużej ilości danych wejściowych. Elementy do uszeregowania: 1. złożoność kwadratowa, 2. złożoność logarytmiczna, 3. złożoność liniowo-logarytmiczna, 4. złożoność liniowa, 5. złożoność stała
Uporządkuj poniższe złożoności obliczeniowe od najszybszej do najwolniejszej dla dużej ilości danych wejściowych. Elementy do uszeregowania: 1. złożoność kwadratowa, 2. złożoność logarytmiczna, 3. złożoność liniowo-logarytmiczna, 4. złożoność liniowa, 5. złożoność stała
3
Ćwiczenie 8
R13T0qXhtfFqO
Połącz w pary algorytmy z odpowiadającymi im złożonościami obliczeniowymi. wyszukiwanie binarne Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa wyszukiwanie najmniejszej liczby w zbiorze Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa sortowanie przez scalanie Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa dodawanie dwóch liczb całkowitych Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa
Połącz w pary algorytmy z odpowiadającymi im złożonościami obliczeniowymi. wyszukiwanie binarne Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa wyszukiwanie najmniejszej liczby w zbiorze Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa sortowanie przez scalanie Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa dodawanie dwóch liczb całkowitych Możliwe odpowiedzi: 1. złożoność logarytmiczna, 2. złożoność liniowo-logarytmiczna, 3. złożoność stała, 4. złożoność liniowa