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()
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.
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.