Wat is de tijdcomplexiteit van terwijl lussen?

Ik probeer de tijdcomplexiteit van terwijl lussen te vinden en ik heb geen idee waar te beginnen. Ik begrijp hoe je de complexiteitsklasse van voor lussen kunt vinden, maar als het om loopt, word ik helemaal verloren. Alle advies / tips over waar te beginnen?

Hier is een voorbeeld van een probleem:

x = 0;
A[n] = some array of length n;
while (x != A[i]) {
   i++;
}

Antwoord 1, Autoriteit 100%

Wanneer u iets moet doen nTIJDEN, moet u het doen nTIJDEN. U kunt een forlus, een whilelus of wat dan ook uw programmeertaal (of pseudo-code!) Aanbiedingen.
Groude, grote O Notation-opmerkingen over de hoeveelheid werk die je moet doen, en geeft er niet om hoe je het doet (enigszins minder gruwelijk, het is opmerkingen over hoe de hoeveelheid werk die gedaan moet worden groeit met de groeiende input) .

Houd lees voor de details.

Ik denk dat je hier dingen verwarren.
forEN whilePROGRAMMERING Taalconstructen om operaties te uiten die moeten worden herhaald.

Algoritme-analyse is agnostisch van de uitvoeringstaal en geeft niet om de werkelijke constructies die u gebruikt tijdens het uiten van het algoritme.

Overweeg volgen:

1. Input n
2. Do OperationX n times

De BIG O NOTATIE-machines helpt u bij het reageren op de complexiteit van de bovenstaande bediening. Dit helpt in veel gevallen. Het kan u bijvoorbeeld helpen bij het vergelijken van de looptijd van de bovenstaande bediening met het volgende:

1. Input n
2. Input m
3. Repeat m OperationX n times.

De grote O-notatie zal u vertellen dat de eerste O (n) is en de laatste is O (m * n) (ervan uitgaande dat OperationXeen constante tijd heeft).

U kunt de code schrijven met behulp van de lusconstructie van uw keuze, het maakt niet uit.

for(int i = 0; i < n; i++) {
    operationX;
}

is de eerste bewerking en

i = j = 0;
while(i < n) {
    j = 0;
    while(j < m) {
      operationX;
      j++;
    }
    i++;
}

de tweede. De grote O Notation maakt het niet echt om als de voor en terwijl het is omgeschakeld.

A[n] = some array of length n;
for(x = 0;x != A[i];i++) {
}

is een foropnieuw schrijven van uw vraag met dezelfde complexiteit (O(n)).