algoritme kompleksitet

Kompleksiteten af hvilken operation ?

Umiddelbart vil jeg da sige:

            vector        list      map
add          O(1)        O(1)      O(1)
get          O(1)        O(n)      O(n)
find        O(n)        O(n)      O(1)

(udelukkende baseret på sund fornuft)

Arne:

Hvorfor er map, get = O(n)

?

get = hente element nummer ix

Jeg formoder at man så er nødt til at løbe igennem indtil man har hentet ix.

Aha, ok.

Nu er jeg ikke så skrap (endnu) til algoritmeanalyse men,
giver det egentlig mening at hente #ix i en map ?

Complexity
There are different measurements of the speed of any given algorithm. Given an input size of N, they can be described as follows:

Name Speed Description

exponential time slow takes an amount of time proportional to a constant raised to the Nth power (K^N)

polynomial time fast takes an amount of time proportional to N raised to some constant power (N^K)

linear time faster takes an amount of time directly proportional to N (K * N)

logarithmic time much faster takes an amount of time proportional to the logarithm of N (log(N))

constant time fastest takes a fixed amount of time, no matter how large the input is (K)


http://www.cppreference.com/complexity.html

kombineret med

Vectors contain contiguous elements stored as an array. Accessing members of a vector or appending elements can be done in constant time, whereas locating a specific value or inserting elements into the vector takes linear time.
http://www.cppreference.com/cppvector.html

Lists are sequences of elements stored in a linked list. Compared to vectors, they allow fast insertions and deletions, but slower random access.
http://www.cppreference.com/cpplist.html

DVS list er hurtigere til at indsætte og slette fra, men langsommere til random access. Hvilket ikke fremgår af Komplesiteten (O(n)). Det er begge dele jeg ønsker at udtale mig om.

Jeg kan godt se spørgsmålet nok ikke var super godt formuleret.

soreno>

Nej - egentligt ikke.

Men som Bent Larsen engang sagde: man skal se meget før der slides
hul i brille glassene !

Særere ting er set før.

O(n) siger kun at tiden er proportional med n når n går mod uendelig.

Ikke noget om om det konstante forhold eller hvor store værdier af n der skal
til førend man nærmer sig det proportionale forhold.

big O analysis kan bruges til at analysere egenskaber ved algoritmer
med hensyn til skalering af data mængder - ikke til at vælge det
hurtigste.

Jeg prøver lige at omformulere:

Jeg har to algoritmer A og B (eksempel)hvor jeg vil bestemme kompleksiteten.

A løber igennem et 2d array (samme som Vector ?), finder et element og for hver element foretages en sammenligning :
Er Kompleksitet O(n^2*n) ?

B gør det samme som A, men slår yderligere op i et Map og finder et objekt. Dette Objekt har en list med fx K = 5 element som løbes igennem. Dette har kompleksitet:
O(n^2* n * n(Map get)* K)?

Anden del er at bestemme hvilken betydning det har at bruge vector frem for list ? (De benyttes ikke kun i disse algoritmer)

jeg tror godt List vs. Vector problematikken kan negligeres for nu :)

Umiddelbart lyder A som O(n^2) og B det samme.

Gennemløb af et 2D array er O(n^2) og resten afhænger som jeg læser det
ikke af n.

arne> gennemløb af 2d array = O(n^2) men der er også den ekstra sammenligning som sker bagefter så hvorfor ikke O(n^2 * n) ?

En sammenligning er jo O(1) - den tid det tager at sammenligne afhænger
ikke af hvor mange elementer der er i det 2D array.

Derfor stadig O(n^2)

Du har selvfølgelig ret Arne.

Jeg har fået besvaret mit spørgsmål så lægger du et svar?

svar