Matematik
algoritmer
Hej, er der nogle, som kan hjælpe med denne opgave?
Svar #1
03. februar 2015 af Soeffi
a) Denne søgning vil kræve, at listen gennemgås fra en ende af (typisk vil det kræve at n/2 navne undersøges). Tidskompleksiteten er lineær.
b) Dette kan foretages som en binær søgning: først vælges et navn i midten af listen, hvis det søgte navn står efter det midterste navn, vælges som næste trin (eller iteration) det midterste navn i sidste halvdel osv. (typisk undersøges log2(n) navne). Da listen halveres for hvert trin er tidskompleksiteten logaritmisk. (Tidskompleksiteten for at sætte navne i alfabetisk orden vil typisk være N·log(N) dvs. lineær gange logaritmisk.)
c) Du har n sprog, som skal forbindes med m oversættelser, i alt n gange m kombinationsmuligheder, dvs. tidskompleksiteten er kvadratisk.
Skriv et svar til: algoritmer
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.