» »

[Naloga] - Algoritmi, časovna kompleksnost

[Naloga] - Algoritmi, časovna kompleksnost

Davidoff ::

A zna kdo rešit ti dve nalogi - res bi bil hvaležen za vsako pomoč!

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?

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

Res hvala!
Pivo Laško vsak dan eno flaško!
  • spremenil: Vesoljc ()

WarpedGone ::

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.
Zbogom in hvala za vse ribe

Davidoff ::

Warped res hvala na odgovoru, ampak pri drugi nalogi gre za eskponentno (n^3) časovno zahtevnost. Ali je potem tudi število operacij 3,6s. To se mi zdi bolj logično za linearno časovno zahtevnost(n). Hvala še enkrat!
Pivo Laško vsak dan eno flaško!

OwcA ::

Č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.
Otroška radovednost - gonilo napredka.

Phil ::

100x hitrejši računalnik opravi isto število operacij v eni stotini časa => 1/100 * 1 ura = 3,6 sekunde.

Typo najbrž, 3600/100 = 36s.
LP

WarpedGone ::

Hvala.

Sm reku, da sm brez kalkulatorja :)
Zbogom in hvala za vse ribe

Davidoff ::

Pol je pri drugi nalogi časovna zahtevnost 100% ne vpliva na rešitev čeprav je eksponentna in rešitev je 36s! ;) In res hvala vsem!
Pivo Laško vsak dan eno flaško!

Nerdor ::

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 :\
... for lifetime!

Zgodovina sprememb…

  • spremenil: Nerdor ()

Senitel ::

Iščeš logaritem 100 pri osnovi 2, sicer nimam Mathematice pri roki, ampak Log[2] je naravni logaritem iz 2...

Nerdor ::

Senitel: yep, če vtipkam Log[2, 100] // N, dobim vn rezultat 6.64386 :)
... for lifetime!

Davidoff ::

Logaritem z osnovo 2 in eksponentom 100 je res 6,6438562...

Še postopek:

1. log(2)100 = x
2. 100 = 2·x
3. log 100 = log2 · x
4. log 100 = x · log 2
5. x = log100 / log2
x = 6.6438562
Pivo Laško vsak dan eno flaško!

arjan_t ::

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.

whatever ::

A lahk še men kdo pomaga? Zanima me, za kaj se uporablja veliki delta (n) pri računanju časovne zahtevnosti oziroma definicija veliki delta(n).
Veliko jih je notri, še več jih je pa zunaj.
Bilijarde v šole! - Ivan Kramberger
Abnormal behaviour of abnormal brain makes me normal.

G_mAn ::

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.

MisterR ::

Imam nekaj primerov, katerih si ne znam pravilno razložiti, bi mi lahko kdo pomagal?
Katere izmed njih imajo zahtevnost reda O(n)?
1.
for(int i=0; i<log(n); i+=3)
{x++;}

2.
for(int i=0;i<n;i++)
{x++}
for(int i=-n;i<0;i++)
{x++}

3.
for(int i=0; i<n-2*i;i++)
{x++;}

4.
for(int i=-n;i<0;i++)
{ 
for(int j=0;j<n/2;j++){x++;}
}

5.
int i=5; while(i<n/5){x++;i+=2;}

Spura ::

2, 3, 5

MisterR ::

Spura seveda me zanimajo rešitve ampak bolj me zanima postopek kako priti do njih.

Kdorkoli?

Zgodovina sprememb…

  • spremenil: MisterR ()

darkkk ::

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).

Zgodovina sprememb…

  • spremenil: darkkk ()

Spura ::

Sicer odvisno kako vzames. O(logn) = O(n), torej naceloma je tut prvi primer O(n). Jst zdej ne vem kaj pricakujejo.

Mavrik ::

Jap, O(logn) je po definiciji tudi O(n).
The truth is rarely pure and never simple.

hexor ::

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?
RootMachine ;)

WarpedGone ::

Da.
Zbogom in hvala za vse ribe

Mavrik ::

hexor: Prav imaš - pri uravnoteženem drevesu bo O(log(n)) (zaradi globine, ki je log(n)), pri neuravnoteženem, ki se lahko izroji v seznam pa O(n).
The truth is rarely pure and never simple.

Spura ::

hexor je 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.

WarpedGone ::

Urejen ja, problem je, da je lahko hkrati tudi "izrojen".
Če maš prazno drevo, ki deluje na relaciji "večji" in vanj pofutraš elemente po vrsti od najmanjšega do največjega al pa obratno, boš dobil navaden seznam in ne drevesa. Je čist urejen ampak iskanje po njemu bo O(n)
Zbogom in hvala za vse ribe


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[c++] naloge

Oddelek: Programiranje
475789 (4329) technolog
»

Časovna zahtevnost

Oddelek: Programiranje
222913 (2457) technolog
»

Algoritmi - časovna zahtevnost

Oddelek: Šola
111709 (1209) FireSnake
»

C++, časovna zahtevnost

Oddelek: Programiranje
51684 (1553) ERGY
»

Grafi (Kruskal, Dijkstra,...)

Oddelek: Programiranje
92307 (2190) Realist

Več podobnih tem