Jednym z najpopularniejszych algorytmów porządkowania jest sortowanie przez wstawianie.
W tym zadaniu odwołujemy się do zapisu algorytmu podanego poniżej:
Dane:
n – dodatnia liczba całkowita
A[1..n] – tablica zawierająca ciąg n liczb całkowitych x1, x2, …, xn, gdzie A[ i ] = xi
Wynik: tablica A zawierająca te same dane, ale uporządkowane niemalejąco, tzn. dla każdego i = 2, …, n, A[ i ] ≥ A[ i – 1]
Uwaga: przyjmij, że jeśli warunek ( j > 1) nie jest spełniony, to warunek (v < A[ j – 1]) nie jest już sprawdzany.
Na potrzeby tego zadania przyjmiemy, że przypisanie A[ j ] ← A[ j – 1] jest operacją dominującą.
Podaj właściwą odpowiedź spośród podanych.
Pesymistyczna złożoność obliczeniowa algorytmu SortW mierzona liczbą operacji dominujących jest:
A. sześcienna.
B. kwadratowa.
C. liniowa.
D. logarytmiczna.
cena_gazu.txt czestosc.txt dane1_3.txt dane1_4.txt dane2_3.txt dane2_4.txt dane3.txt dane4.txt dane6.txt dane6przyklad.txt dane8.txt gaz.txt pracownicy.txt rejestr_aktywnosci.txt szyfrogram.txt zamowienia.txt
W tym zadaniu odwołujemy się do zapisu algorytmu podanego poniżej:
Dane:
n – dodatnia liczba całkowita
A[1..n] – tablica zawierająca ciąg n liczb całkowitych x1, x2, …, xn, gdzie A[ i ] = xi
Wynik: tablica A zawierająca te same dane, ale uporządkowane niemalejąco, tzn. dla każdego i = 2, …, n, A[ i ] ≥ A[ i – 1]
Algorytm SortW:
dla i = 2, 3, …, n wykonaj:
v ← A[ i ]
j ← i
dopóki (j > 1) oraz (v < A[ j – 1]) wykonaj:
A[ j ] ← A[ j – 1]
j ← j - 1
A[ j ] ← v
Uwaga: przyjmij, że jeśli warunek ( j > 1) nie jest spełniony, to warunek (v < A[ j – 1]) nie jest już sprawdzany.
Na potrzeby tego zadania przyjmiemy, że przypisanie A[ j ] ← A[ j – 1] jest operacją dominującą.
Podaj właściwą odpowiedź spośród podanych.
Pesymistyczna złożoność obliczeniowa algorytmu SortW mierzona liczbą operacji dominujących jest:
A. sześcienna.
B. kwadratowa.
C. liniowa.
D. logarytmiczna.