Złożoność algorytmu

Witam,
Czy mógłby ktoś mi policzyć złożoność tego algorytmu
Wg moich obliczeń wynosi N^2 lecz Pani Profesor uważa inaczej ponieważ twierdzi że "powinno być policzone na liczbach i zamianst ogólnej literki N ma być konkretne zmienne z tego kodu

for i = 111 to 999
   for j = 111 to 999
      x = 3cyfra_j
      y = 2cyfra_j
      z = 1cyfra_j
 if x*i < 1000 
         if 1000 <= y*j <= 9999 
            if z * i < 1000 
               if 100000 < i * j < 999999
                  l1 = 2cyfra_ij
                  l2 = 5cyfra_ij
                  if l1 = 9 and l2 = 1
                     wypisz i, j, i*j
                     zakończ

Pani Profesor uważa inaczej ponieważ twierdzi że "powinno być policzone na liczbach i zamianst ogólnej literki N ma być konkretne zmienne z tego kodu

IMHO pani profesor niech się leczy -_-'

W twojej odpowiedzi też jest niestety błąd. Złożoność tutaj to O(n^2), a nie n^2.

Zauważ, że w ifach nie ma już kolejnych pętli, jeśli uznamy, że jedynym faktycznym rozkazem tu jest wypisz i, j, i*j (porównania raczej się nie liczą), to mamy tu O(1 * n^2)</code>. A nawet gdyby tych operacji było więcej (albo gdyby uznać operację przypisania za rozkaz, a nie pamiętam, czy powinno się), to byłoby O(C * n^2), a jak wiadomo, <code>O(C * n^2) === O(n^2).

Może ona cię pyta o liczbę kroków, a nie o złożoność obliczeniową?

A jesteś pewien ze dobrze ją zrozumiałeś? Może jej chodziło o policzenie złożoności razem ze stałymi?
Ale jak ma być na liczbach co tu liczyć? Rząd złożoności obliczeniowej to jest funkcja zmiany czasu wykonania algorytmu w zależności od zmiany rozmiaru danych wejściowych. Nie da się podać złożoności dla konkrentych liczb bo to by nie miało sensu. Można za to policzyć ile jest porównań i przypisań.

Zacznijmy od tego że tu nie za bardzo cokolwiek (tzn. jakieś n) dąży do nieskończoności - same stałe.
Może chodzi po prostu o np. obliczenie ile obrotów pętla wykona przed:

wypisz i, j, i*j
zakończ # zakończ działanie algorytmu?

@aurel - ja potrafię ;P
2^3 albo 2³ albo

To w takim razie ile będzie tu obrotów pętli ?