[php] fibonacci a złożoność Opcje

[hhg]

na stronie wikipedii na samym dole:
http://pl.wikipedia.org/wiki/Algorytm_Euklidesa

czytam:
<quote>Ciekawostki
* Największej liczby kroków algorytmu wymagają dwa kolejne elementy ciągu Fibonacciego</quote>

w takim razie dlaczego mój skrypt:

[PHP] pobierz, plaintext 
<?php
 
include('funkcje.inc');
 
$time = array();
$operation = array();
$max = 8;
 
// ciag fibonacciego a NWD
for ($i = 1; $i < $max; $i++)
{
		$time_start = getmicrotime();
		$operation[$i] = dif_ite(fib($max),fib($i));
 
		$time_end = getmicrotime();
 
		$time[$i] = round($time_end - $time_start,5);
		echo 'Dla fib(' . $i . ') oraz fib(' . $max . ') czas wykonania operacji NWD algorytmu Euklidesa zajal ' . $time[$i] . ' sekund.<br /><br />';
}
 
 
?>
[PHP] pobierz, plaintext 

gdzie include('funkcje.inc'); są tu:

zwraca wyniki takie:

co prawda czas niby rosnie ale chodzi o złożonośc = liczbe operacji. A ta maleje!!

co robie źle?

Ten post edytował hhg 28.08.2007, 00:12:28

[Nigger]

Jedne operacje np mnożenie zajmują kilkanascie razy więcej cykli zegarowych niż inne np dodawanie ...
A pozatym to co Ty piszesz to jest bardzo mało prawdopodbne. W 99,999 % przypadkach złozoność idzie w parze z czasem.

Ten post edytował Nigger 21.04.2007, 09:15:32

[Hacker]

[PHP] pobierz, plaintext 
<?php
dif_ite(fib($max),fib($i));
?>
[PHP] pobierz, plaintext 

na

[PHP] pobierz, plaintext 
<?php
div_ite(fib($max),fib($i));
?>
[PHP] pobierz, plaintext 

i złożoność jest taka, jaka ma być