[Naloga] - Algoritmi, časovna kompleksnost

1.) Nek algoritem ima cas. zahtevnost 2^n. V nekem casu T lahko resimo problem velikosti n1. Za koliko vecji problem lahko resimo v taistem casu T, ce kupimo 100krat hitrejsi racunalnik?

Isti čas na stokrat hitrejšem računalniku je ekvivalenten stokrat več časa na istem računalniku. Če ima algoritem zahtevnost 2^n, problem velikosti N1 pa porabi čas T to pomeni: 2^N1 = T. Iščemo pa tak N2, da je 2^N2 = 100T

Torej:
2^N2 = 100 * 2^N1
100 = 2^N2 / 2^N1
100 = 2^(N2 - N1)
(N2 - N1) = log(2) 100
N2 = N1 + log(2) 100
N2 = N1 + 6.65

Za 6.65 večji problem. (tole je brez kalkulatorja, ne garantiram za cifre)

2.) Casovna zahtevnost je 3^n. Racunalnik opravi 100 operacij v 1 uri. V koliksnem casu pravi teh 100 operacij 100x hitrejsi racunalnik.

Časovna zahtevnost tu ne igra vloge. 100x hitrejši računalnik opravi isto število operacij v eni stotini časa => 1/100 * 1 ura = 3,6 sekunde.

Časovna zahtevnost poveže število vhodnih podatkov s številom operacij.

Hitrost računkega stroja poveže število operacij s časom.

Pri 2. nalogi je število vhodnih podatkov ves čas enako, torej nas časovna zahtevnost ne zanima.

Hvala.

Sm reku, da sm brez kalkulatorja :)

Ti WarpedOne in davidoff, meni program Matematika za enačbo Log[2]*100 vrne (0.693147)*100 = 69.3147
Zanima me, ali sem pravilno zastavil formulco

Senitel: yep, če vtipkam Log[2, 100] // N, dobim vn rezultat 6.64386

Malo pomoči :)

1. Algoritem je sestavljen iz treh delov. Prvi del algoritma je bil ocenjen s
časovno zahtevnostjo T1 (n) = 100n 2 , drugi del T2 (n) = 10n log 2 n T, tretji del
pa je bil ocenjen s T3 ( n) = 0.00123n 3 . Ocenite skupno časovno zahtevnost
tako, da uporabite funkcijo veliki O.
2. Izračunajte čas računanja algoritma, če ima časovno zahtevnost T (n) = n5 .
Obsežnost problema je 45, čas ene operacije pa je 1 µs.

Hmm te časovne zahtevnosti res niso tako lahke, sem poizkušal reševati podobne naloge in kaj vem ne znam preveč, ker niti nevem kake enačbe uporabiti in postopke. Tako da če zna kdo in bi bil tako dober, bi prosu če lahko napiše postopek za kakšno izmed nalog.

Hvala.

2, 3, 5

1. narediš log(n) korakov zanke, ki se izvede v konstantnem času, torej log(n).

2. maš dve zanki, vsaka ima n korakov, ki se spet izvedejo v konstantnem času => O(2n) = O(n)

3. spet maš zanko, ki teče do n-neki, ampak te stvari so še vedno reda O(n). (drgač pej aritmetično zaporedje seštet pa boš dobil da je neki linearno v n)

4. zahtevnosti O(n^2), zunanja zanka ima n korakov, vsak traja n/2.

5. spet maš neko linearno zadevo, pač ne greš do n ampak le do "n/5" pa greš le po lihih indeksih, ampak to te ne zanima, pač bo reda O(n/10), ampak je še vedno O(n).

Jap, O(logn) je po definiciji tudi O(n).

Da.

hexor je 28. jun 2012 ob 13:28 izjavil:

Ko se tukaj o časovni kompleksnosti pogovarjate, imam tudi sam eno vprašanje.Kolikšna je najslabša možna časovna zahtevnost iskanja nekega elementa v urejenem/neurejenem binarno iskalnem drevesu? Sam sklepam, da iskanje v urejenem BST temelji na bisekciji, torej O(log(n))v najslabšem primeru(analogija z globino drevesa), pri neurejenem BST se pa vse skupaj obnaša kot nek seznam, ki ima v najslabšem primeru časovno zahtevnost O(n)->preiščemo vse elemente.Ali drži moja domneva vodo, ali ne?

BST je vedno urejen.