logn vs n


beäntweren 1:

Ech sinn en Ufänger beim Programméiere awer äntwer dëst, well et e ganz Basis Wëssen ass.

Als éischt verstitt Dir datt d'Big-O Notatiounen gi benotzt fir d'Zäitkomplexitéit vun engem Computerprogramm ze representéieren.

Zäitkomplexitéit gëtt fir n = ganz grouss analyséiert.

O (1) heescht eng konstant Zäit ze lafen egal wat de Wäert vun n ass.

O (n) bedeit déi Zäit, déi geholl gëtt, wuesse lineär mat n.

Beispill: Zomm vun den éischte n natierlechen Zuelen Et ginn zwou Léisunge fir de Problem 1) andeems d'Formel n (n + 1) / 2 Déi Zäit geholl ass O (1)

2) Iteration ze benotzen Sum = 0 Fir i <- 1: n Sum = Sum + i Déi eng Schrëtt géif huelen. Bedeitung Zäit Komplexitéit = O (n)

Natierlech wann n wuessen O (n) wäert méi Zäit daueren wéi O (1)

Awer a verschiddene Fäll leeft O (n) méi séier fir e ganz klenge Wäert vun n.