Wyrazić złożoność obliczeniową T(n) poniższego algorytmu w notacji Θ.
Kod: Zaznacz cały
for i <-- 1 to n
j <-- 1
while j <= 2 * i
do
a <-- i + j
j <-- j + 1
Zad. 2. Rozważmy alfabet A = {1,2,3} oraz wzorzec P = 33213. Podać przykład możliwie najkrótszego tekstu T, w którym wzorzec P występuje z co najmniej 3 różnymi nieparzystymi przesunięciami.
Zad. 3. W trakcie sortowania (rosnąco) 8-elementowego ciągu liczb naturalnych: 44, 55, 12, 42, 94, 18, 6, 67, otrzymano następujący ciąg (częściowo uporządkowany):
6, 12, 18, 42, 94, 55, 44, 67.
Czy algorytm sortowania przez wstawianie mógł być w tym przypadku zastosowany? Dlaczego?