1 svar
77 visningar
oZwap behöver inte mer hjälp
oZwap 4
Postad: 23 feb 2022 13:34

Komplexitet vid for-loopar

Snabb fråga.

Sitter och funderar på hur komplexiteten vid loopar fungerar.

Vet att om man har en loop som ser ut som nedan så är komplexiteten O(n)

for(int i = 0; i < n; i++)
{
	// Code to execute
}

Samt att om man har en nästlad loop som nedan så är komplexiteten O(n2)

for(int i = 0; i < n; i++)
{
	for(int j = 0; j < n; j++)
	{
		// Code to execute
	}
}

 

Om vi då kollar på fallet att man byter ut n mot låt säga 100. Är komplexiteten fortfarande O(n) eller räknas det som O(1). Alltså om man skriver loopen som nedan.

for(int i = 0; i < 100; i++)
{
	// Code to execute
}

För som jag fattat de så räknas komplexiteten som konstant om de alltid tar lika lång tid att köra ett stycke kod.

Laguna Online 30472
Postad: 23 feb 2022 16:39

Ja, finns det inget n som påverkar tiden och som kan varieras så är tiden konstant. (Den kan påverkas av slumpmässigheter i indata, men det ligger utanför den här frågan.)

Det gäller inte bara for-loopar utan alla program.

Svara
Close