[Teoria złożoności] Wyrazić złożoność obliczeniową T(n)

[Ikaa]

Zad. 1.
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 

Uwaga: wszystkie zmienne są liczbami całkowitymi.


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?

[Elon]

Ikaa studiujesz informatykę na UJ?

[wiem]

1) Złożoność czasowa w tej notacji wynosi \(\displaystyle{ n^{2}}\)
3) nie bo sortując przez wybór nie zamienilibyśmy miejscami 44 i 55

[Ikaa]

dziękuje bardzo