CIO Tech Eksperten IT-JOB IT-Kurser Events Podcast Søg

Log ind eller opret profil

Du kan også logge ind via nedenstående tjenester

casualty Nybegynder

13. maj 2003 - 23:05 Der er 8 kommentarer og
1 løsning

Rekursion logaritmer og store O notationen

I forbindelse med min uddannelse har vi snakket en del om rekursive funktioner. Disse bliver oftest vist ved store O notationen?? Det hele bygger på logaritmiske funktioner, men jeg har lykkelig glemt hvad en logaritme er... Er der én der kan forklare det "from scratch" Jeg har haft Matamatik på B niveau for et år siden men jeg husker ikke en bjælde...

Mvh Casualty

Synes godt om

arne_v Ekspert

13. maj 2003 - 23:10 #1

big O er egenskaberne ved en algoritme.

En algoritme der er O(n) vokser CPU/memory lineært med størrelsen
af data.

10-tals logaritmen har følgende egenskaber:

log10(1)=0
log10(10)=1
log10(100)=2
log10(1000)=3

2-tals logaritmen har følgende egenskaber:

log2(1)=0
log2(2)=1
log2(4)=2
log2(8)=3
log2(16)=4

Det er en funktion som vokser mindre end lineært.

Synes godt om

casualty Nybegynder

13. maj 2003 - 23:14 #2

Så er dette korrekt antaget?

log5(1)=0
log5(5)=1
log5(25)=2
log5(125)=3

Synes godt om

casualty Nybegynder

13. maj 2003 - 23:15 #3

Hvad er o og hvad er n Er det mæmgden af data og hvad?

Synes godt om

arne_v Ekspert

13. maj 2003 - 23:18 #4

O er bare noget man kalder det.

n = antal elementer, antal records, antal et eller andet

Synes godt om

casualty Nybegynder

13. maj 2003 - 23:18 #5

Hvis nu jeg har en rekursiv metode således:

public int div1(int n,int m,int res)
{
if (n<m)
{
return res;
}
else
{
return div1(n-m,m,res+1);
}
}

Hvorledes vil den se ud ifølge logaritmer o(n)???

Synes godt om

arne_v Ekspert

13. maj 2003 - 23:23 #6

Umiddelbart vil jeg tror at den er O(n) d.v.s. slet ikke
noget logaritme.

Bobblesort er O(n*n) mens Quicksort er O(n*log(n)).

Synes godt om

arne_v Ekspert

13. maj 2003 - 23:23 #7

Den er O(n) fordi hvis n fordobles (og m er konstant) så vil antal
rekursioner også fordobles.

Synes godt om

casualty Nybegynder

13. maj 2003 - 23:24 #8

Ok..Jeg tror at jeg fatter lidt mere nu...Tak for hjælpen

Synes godt om

jakoba Nybegynder

14. maj 2003 - 00:09 #9

en lille O(n*n)

public int fibonacci( int n ) {
if ( n < 0 ) System.out.println( "FEJL. n skal være >= 0" );
if ( n <= 0 ) return 0;
if ( n == 1 ) return 1;
return fibonacci(n-2) + fibonacci(n-1);
}

prøv den med diverse parameterværdier, så vil du opdage at det VIRKELIG er en god ide at lede efter en O(n*log(n)) eller endnu bedre O(n) algoritmer.

mvh JakobA

Synes godt om

Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Følg dette spørgsmål

Opret Preview

Programmeringssprog kurser

Kurser inden for grundlæggende programmering

Se alle Programmeringssprog kurser

Flere spørgsmål fra Andet programmering kategorien

Titel	Indlæg	Oprettet	Seneste aktivitet
Bat-fil / vbs til ændre af filnavn udfra mappe-navn Af tjodense i Andet programmering	3	10/04/202511:18	11/04/202513:49
Echo virker ikke i php Af KurtG i Andet programmering	10	23/02/202511:57	24/02/202510:01
Rewrite i .htaccess til Joomla 5 Af andrew i Andet programmering	5	15/01/202520:23	16/01/202522:59
Kodning af element i custom css Af Jacob Hedelund i Andet programmering	3	14/10/202410:35	14/10/202419:46
Delphi 11 - converter webp til jpg fil Af juzas i Andet programmering	5	12/10/202413:28	14/10/202403:54

Se alle spørgsmål i kategorien Opret spørgsmål

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester

Alle kategorier på Eksperten

Seneste artiklerRSS