Forum » Programiranje » Casovna kompleksnost algoritma
Casovna kompleksnost algoritma
bajsibajsi ::
FOR i = 1 to (n-1)
FOR j = 1 to (n+1)
.....
next j
next i
(n je celo število >0) Resitev: Tk ∝ n-1 ali n^2-1 ?
-----------------------------------------------------
i=0
Do
i=i+2
n=n+1
...
loop until i>n
Tk je linearna? n se v vsaki zanki poveca za 1, zato zgornja meja ni tocno dolocena. Resitev?
----------------------------------------------------
i = 0
Do While i < n
i = i + 2
.........
Loop
(pri ....se n, i ne spreminjata; n je pozitivno celo število>0)
Tk = ?
----------------------------------------------------
For k=1 to (n/2)
...
Next k
For i=1 to n
For j=1 to n
...
Next j
Next i
Resitev: Tk ∝ n*n + (n/2) Prav?
--------------------------------------------------
i = 3
Do
i = i + 0.5
Loop Until i > n
Resitev: Tk ∝ (n − 3) ∙ 2 + 1 Prav?
--------------------------------------------------
For i = n To 1 Step -1
For j = 1 To i
Next
Next
Tk ∝ n*(n+1)/2
FOR j = 1 to (n+1)
.....
next j
next i
(n je celo število >0) Resitev: Tk ∝ n-1 ali n^2-1 ?
-----------------------------------------------------
i=0
Do
i=i+2
n=n+1
...
loop until i>n
Tk je linearna? n se v vsaki zanki poveca za 1, zato zgornja meja ni tocno dolocena. Resitev?
----------------------------------------------------
i = 0
Do While i < n
i = i + 2
.........
Loop
(pri ....se n, i ne spreminjata; n je pozitivno celo število>0)
Tk = ?
----------------------------------------------------
For k=1 to (n/2)
...
Next k
For i=1 to n
For j=1 to n
...
Next j
Next i
Resitev: Tk ∝ n*n + (n/2) Prav?
--------------------------------------------------
i = 3
Do
i = i + 0.5
Loop Until i > n
Resitev: Tk ∝ (n − 3) ∙ 2 + 1 Prav?
--------------------------------------------------
For i = n To 1 Step -1
For j = 1 To i
Next
Next
Tk ∝ n*(n+1)/2
- spremenilo: bajsibajsi ()
Math Freak ::
Pri prvi dobiš: (n-1)*(n+1) = n2 - 1.
Pri drugi - primer:
n = 6
i = 0
Dokler i ni večji od n, povečuj n za 1, i za 2.
(n,i) = (7,2),(8,4),(9,6),(10,8),(11,10),(12,12),(13,14).
Potreboval si 7 korakov, torej n+1.
Pri tretji - primer:
n = 9
i = 0
Dokler je i manjši od n, povečuj i za 2.
(n,i) = (9,2),(9,4),(9,6),(9,8),(9,10)
Potreboval si 5 korakov, torej,
če je n sodo: n/2.
če je n liho: n/2 + 1/2.
Pri drugi - primer:
n = 6
i = 0
Dokler i ni večji od n, povečuj n za 1, i za 2.
(n,i) = (7,2),(8,4),(9,6),(10,8),(11,10),(12,12),(13,14).
Potreboval si 7 korakov, torej n+1.
Pri tretji - primer:
n = 9
i = 0
Dokler je i manjši od n, povečuj i za 2.
(n,i) = (9,2),(9,4),(9,6),(9,8),(9,10)
Potreboval si 5 korakov, torej,
če je n sodo: n/2.
če je n liho: n/2 + 1/2.
Math Freak ::
Torej:
for i = 1 to 5 pomeni i = 1,2,3,4,5 (zgornja meja - 5, je vključena notri? Ker po navadi v nekaterih programih ni?).
Če je vključena, potem imaš prav ostale naloge.
for i = 1 to 5 pomeni i = 1,2,3,4,5 (zgornja meja - 5, je vključena notri? Ker po navadi v nekaterih programih ni?).
Če je vključena, potem imaš prav ostale naloge.
lebdim ::
če te zanima časovna kompleksnost algoritma, moraš vedno dobiti O(nekaj), pri čemer je ta nekaj lahko: n, n2, log n, n logn, n2logn, 2n, ... itd...
če te pa zanima zgolj število operacij, ki se v tem delu programčka izvede, pa je takole:
- primerjanje je ena operacija (primer: if (a>0) then)
- prirejanje sta dve operaciji (primer: a:=a+2);
- če imamo npr. zanko while:
npr.
v tem primeru se bo zanka while izvedla (N-i+1)-krat: torej (N+1)-krat.
če te pa zanima zgolj število operacij, ki se v tem delu programčka izvede, pa je takole:
- primerjanje je ena operacija (primer: if (a>0) then)
- prirejanje sta dve operaciji (primer: a:=a+2);
- če imamo npr. zanko while:
npr.
i:=0; while (i <= N) do nekaj....
v tem primeru se bo zanka while izvedla (N-i+1)-krat: torej (N+1)-krat.
goldenratio ::
prvi paragram pri 3 je narobe postavljen, pa še struktura pri 8 vrstici je nepotrebna
bajsibajsi ::
Math Freak je izjavil:
Torej:
for i = 1 to 5 pomeni i = 1,2,3,4,5 (zgornja meja - 5, je vključena notri? Ker po navadi v nekaterih programih ni?).
Če je vključena, potem imaš prav ostale naloge.
Zgornja meja je vkljucena notri. Hvala za pomoc. :)
lebdim ::
@bajsibajsi,
torej tista zgornja meja pri for zanki ni v vseh jezikih vključena notri. ti bom razložil s konkretnima primeroma.
Imaš npr. podano for zanko od 1 do N v C:
V tem primeru se bo for zanka še izvedla, ko bo i=N, ko pa bo i=N+1, pa se ne bo več izvedla. Tako da, tukaj zgornja meja N pade v zanko.
Sedaj pa imaš podano enodimenzionalno tabelo celih števil. S for zanko se boš sprehodil po celi tabeli.
V tem primeru pa se bo for zanka še izvedla, ko bo i=N-1, ko bo i=N, pa se ne bo več izvedla. Zakaj pa je temu tako???
-> Zato, ker se v C-ju prvi element v tabeli nahaja na indeksu 0 in je potem dejanska velikost tabele N-1.
Če bi pa programiral npr. v programskem jeziku Pascal, pa s tem ne bi imel nobenih problemov, saj bi bilo vse postavljeno na 1 in tudi zgornja meja bi vedno padla notri.
torej tista zgornja meja pri for zanki ni v vseh jezikih vključena notri. ti bom razložil s konkretnima primeroma.
Imaš npr. podano for zanko od 1 do N v C:
for (i=0; i<=N; i++) {
naredi nekaj ...
}
V tem primeru se bo for zanka še izvedla, ko bo i=N, ko pa bo i=N+1, pa se ne bo več izvedla. Tako da, tukaj zgornja meja N pade v zanko.
Sedaj pa imaš podano enodimenzionalno tabelo celih števil. S for zanko se boš sprehodil po celi tabeli.
int tab[N];
int i=0;
for (i=0; i<N; i++){
naredi nekaj v tabeli ...
}
V tem primeru pa se bo for zanka še izvedla, ko bo i=N-1, ko bo i=N, pa se ne bo več izvedla. Zakaj pa je temu tako???
-> Zato, ker se v C-ju prvi element v tabeli nahaja na indeksu 0 in je potem dejanska velikost tabele N-1.
Če bi pa programiral npr. v programskem jeziku Pascal, pa s tem ne bi imel nobenih problemov, saj bi bilo vse postavljeno na 1 in tudi zgornja meja bi vedno padla notri.
Zgodovina sprememb…
- spremenil: lebdim ()
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | časovna kompleksnost-razlagaOddelek: Programiranje | 2285 (1530) | aaa1 |
| » | Stevilo kvadratov vzorcaOddelek: Šola | 2129 (1763) | lebdim |
| » | [c++] nalogeOddelek: Programiranje | 5628 (4168) | technolog |
| » | Matematika - FMF (strani: 1 2 )Oddelek: Šola | 10036 (7769) | sherman |
| » | Matematično vprašanje v zvezi s lotomOddelek: Programiranje | 1926 (1594) | OwcA |