» »

časovna kompleksnost-razlaga

časovna kompleksnost-razlaga

m3jbi ::

Lepo pozdravljeni!

Prosim za pomoč pri rešitvi in razlagi naslednjih nalog (postopek kako se razreši).

1. Ocenite časovno kompleksnost naslednjega algoritma:
i=0
Do While i < n
i = i+2
......
Loop

2. Izračunaj časovno kompleksnst:
i=0
Do
i = i+2
n = n+1
.....
Loop until i>n

3.
FOR i = 1 to (n-1)
FOR j = 1 to (n+1)
.....
next j
next i

4.
FOR k = 1 to (n/2)
.....
Next k
FOR i = 1 to n
FOR j = 1 to n
.....
Next j
Next i

Hvala in lep pozdrav.

epsilon ::

Formatiranje kode ti ne gre najboljse :P

1. Loop se izvede n/2-krat, torej O(n)
2. O(n); verjetno je na izpitu pametno pokazat, da je 2*k > n+k za k > n, kar ti da stevilo iteracij glede na spreminjanje i in n.
3. (n-1) * (n+1) = O(n^2); zunanji loop se izvede n-1-krat, ob vsaki izvedbi se se notranji n+1-krat
4. n/2 operacij za prvi loop po k, nested loop je O(n^2) z enakim razmislekom kot pri (3). Torej O(n/2) + O(n^2) = O(n^2)

Drugac pa to je FERI? Ali je Kononenko presel na VB? :D

Blinder ::

Dej skensli tole in pejt raje na morje. Tega v zivljenju ne bos nikoli potreboval. To je kriminal da vam serjejo v lobanjo take stvari.
99.991% of over-25 population has tried kissing.
If you're one of the 0.009% who hasn't, copy & paste this in your Signature.
Ryzen 1700 gtx 970 Pismo smo stari v bozjo mater. Recesija generacija

St753 ::

Blinder je izjavil:

Dej skensli tole in pejt raje na morje. Tega v zivljenju ne bos nikoli potreboval. To je kriminal da vam serjejo v lobanjo take stvari.

Pri vseh intervjujih za sluzbo, ki sem jih imel, sem dobil kaksno vprasanje na to temo. Ce tvoj cilj ni ostati brez sluzbe, bi rekel, da tvoja trditev ne drzi.

m3jbi ::

Ja rabim za izpit (VB), pa mi nikakor ni bilo jasno. V rešitvah naj bi dobili alfo.
Torej
1. Tk=?.n
2. Tk=linearna
3. Tk=? n-1
4. Tk=?.n+n
Hvala za odgovor ?

epsilon ::

Kaj ko bi ti tole nalogo slikal, da dejansko vidimo, kaj od tebe hoce? :)

Ker dolocit alpho (ce tu govorimo o konstanti), da je alpha*n = n^2 za vse x (3, 4 primer), pac ni mozno. Pa se to pri asimptotiki ni pomembna. Ce pa dejansko stejemo operacije za konkreten n, pol je pa se kako vazno, kaj se skriva v tistih pikicah v prvem postu.

Zgodovina sprememb…

  • spremenilo: epsilon ()

m3jbi ::

Žal so to cela navodila :(

Blinder ::

Tak je ko fakulteti ni v interesu da bi odsli s faksa s cimvec znanja.
99.991% of over-25 population has tried kissing.
If you're one of the 0.009% who hasn't, copy & paste this in your Signature.
Ryzen 1700 gtx 970 Pismo smo stari v bozjo mater. Recesija generacija

smacker ::

Lažje je tožit, da je nekaj neuporabno, kot pa se poglobit v področje. Znanje se žal ne streže na krožniku, kot mamino kosilo. Treba zavihat rokave pa bo. Gradiva na to temo je ogromno.

AndrejO ::

Blinder je izjavil:

Tak je ko fakulteti ni v interesu da bi odsli s faksa s cimvec znanja.

Fakulteta ti da:
- Posebej ure za vaje, kjer se takšna vprašanja praktično obdela.
- Asistente, ki jih lahko kadarkoli vprašaš za dodatno razlago ali pomoč.
- Govorilne ure pri predavateljih, ki jih lahko porabiš tudi za takšna vprašanja.
- Sošolce, da se lahko skupaj z njimi učiš.
- Možnost večkratnega brezplačnega opravljanja izpita, če ti prvič ne uspe.

Fakulteta ti ne da:
- Vsega na srebrnem pladnju.
- Delovnih navad.

Invictus ::

Blinder je izjavil:

Tak je ko fakulteti ni v interesu da bi odsli s faksa s cimvec znanja.

To sam jamrajo tisti, ki se niso sposobni nič naučiti...

In tisti mali privatnički, ki bi radi, da jim fakulteta priskrbi poceni obrtniško delovno silo, ki zna nek obskurni PHP/javascript/DB framework...

Ker drugače bo novo zaposleni diplomiranec hitro spoznal, da je njegov šef budala, ki se mu je slučajno usralo...
"Life is hard; it's even harder when you're stupid."

http://goo.gl/2YuS2x

bajsibajsi ::

Blinder je izjavil:

Dej skensli tole in pejt raje na morje. Tega v zivljenju ne bos nikoli potreboval. To je kriminal da vam serjejo v lobanjo take stvari.


Aja?

Malo offtopic a vseeno podobno. EXCEL - poiskati besedni nizv koloni in vrstico kopirati na drugi list Predstavljaj si, da ima OP v tisti temi na tisoce vrstic podatkov in vedno znova dela proces, ki lahko zahteva ure in ure dela. Koda, ki sem mu jo napisal, njegovo zagato vsakic resi v nekaj sekundah.

neverlucky ::

bajsibajsi je izjavil:

Blinder je izjavil:

Dej skensli tole in pejt raje na morje. Tega v zivljenju ne bos nikoli potreboval. To je kriminal da vam serjejo v lobanjo take stvari.


Aja?

Malo offtopic a vseeno podobno. EXCEL - poiskati besedni nizv koloni in vrstico kopirati na drugi list Predstavljaj si, da ima OP v tisti temi na tisoce vrstic podatkov in vedno znova dela proces, ki lahko zahteva ure in ure dela. Koda, ki sem mu jo napisal, njegovo zagato vsakic resi v nekaj sekundah.



Seveda da ima ogromno veze. Pac Blinder v zivljenju ni se nikoli napisal nobene stvari, ki bi bila pac racunsko zahtevna. Urejal je sezname s 500 elementi in na svojem racunalniku ni opazil razlike med n^2 zahtevnostjo in nlogn zahtevnostjo.

aaa1 ::

Invictus je izjavil:

Ker drugače bo novo zaposleni diplomiranec hitro spoznal, da je njegov šef budala, ki se mu je slučajno usralo...

S tem citatom, se pa sam tako prekleto poistovetim, da kar res ni. Do sedanjega šihta, kjer imamo res strokovnega šefa, so bili do sedaj vsi neki "samouki" ki so poznali samo eno področje in si jih hitro dobil po prstih če si šel izven ograjice. :) Pa to da je FRI brezveze govorijo samo tisti ki ga niso končali ponavadi. :)


Vredno ogleda ...

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

Neuralink že načrtuje poskuse na ljudeh

Oddelek: Novice / Znanost in tehnologija
256195 (4928) Gregor P
»

Casovna kompleksnost algoritma

Oddelek: Programiranje
71127 (882) lebdim
»

Java metode;

Oddelek: Programiranje
353784 (2976) ragezor
»

Časovna zahtevnost

Oddelek: Programiranje
222440 (1984) technolog
»

[python]kaj je hitreje

Oddelek: Programiranje
81101 (909) Spura

Več podobnih tem