Złożoność obliczeniowa – pomoc i wyjaśnienie zadania

Witam mam pytanie odnosnie zadania 3? A mianowicie zlozonosci. Zlozonosc poerwszego warunku bedzie O(1) ale reszty niestety nie wiem :/ bardzo prosze o pomoc

O(n^2) mi się wydaje

pętla

for (int i=0; i<n; i++)
{
    Console.WriteLine("hello");
}

Ma złożoność n, bo wykona się n razy (dla n=3 wykona się 3 razy)

Jak zrobisz pętle w pętli

for (int i=0; i<n; i++)
{
    for (int y=0; y<n; y++)
    {
        Console.WriteLine("hello");
    }
}

to wykona się ona n*n razy(dla n=3 wykona się 9 razy)

Jak zrobisz pętle w pętli w pętli

for (int i=0; i<n; i++)
{
    for (int y=0; y<n; y++)
    {
        for (int z=0; z<n; z++)
        {
            Console.WriteLine("hello");
        }
    }
}

to wykona się ona n*n*n razy (dla n=3 wykona się 27 razy)

A dlaczego akurat tak? bardzo zalezy mi na zrozumieniu jak sie to liczy

Przez zagnieżdżoną pętlę - https://stackoverflow.com/questions/526728/time-complexity-of-nested-for-loop

Jeśli chodzi o ilość wypisań - i * j jest większe od 0 dla i = 1 i dodatnich j oraz i = -1 i ujemnych j, czyli wychodzi, że wypisze "Hello" dla każdego j oprócz 0.

W Twoim przypadku zewnętrzna pętla wykonuje się zawsze 3 razy (o ile ta końcowa jedynka jest włącznie), co daje kontrybucję 3 do ilości iteracji. Z kolei pętla wewnętrzna wykona się 2n+1 razy (znowu, o ile lecimy do n włącznie), bo leci od -n do -1 (czyli n razy), mija zero (1 raz) i leci od 1 do n (znowu n razy), co daje n+1+n=2n+1. W takim razie łączna liczba iteracji wynosi 3(2n+1)=6n+3. Instrukcja if nie ma wpływu na złożoność obliczeniową, ponieważ wykonuje się zawsze tyle razy, ile jest iteracji.

Przy szacowaniu złożoności obliczeniowej używając większości znanych notacji (duże O, notacja omega i notacja theta) pomija się stałe addytywne i multiplikatywne, co oznacza że możemy wyrzucić 6* oraz +3, co daje nam oszacowanie:

Jeśli chodzi o ilość wypisanych "Hello ", to trzeba spojrzeć na warunek if'a. Iloczyn i oraz j jest większy od zera. Znaczy to, że i oraz j są obie dodatnie, albo są obie ujemne (bo wtedy iloczyn jest nadal dodatni). Sprawdźmy to dla 3 iteracji pętli zewnętrznej:

1. i=-1, czyli j musi być ujemne. Co daje nam wartości od -n do -1, a ich jest n.
2. i=0, czyli cały iloczyn jest zero, więc na pewno nie jest większy od zera.
3. i=1, czyli j musi być dodatnie. Daje nam to wartości od 1 do n, a ich jest n.
   Łącznie iteracji, w których warunek i*j>0 jest spełniony jest n+0+n=2n, czyli "Hello " zostanie wypisane 2n razy.

masz tam dwie pętle.
Pierwsza iteruje zawsze 3 razy (od -1 do 1), co daje czynnik 3, który w notacji o nic nie wnosi.
Druga pętla wykonuje się 2n + 1 razy (od -n do n), więc daje czynnik 2n + 1, który w notacji o daje po prostu n.
Czyli odpowiedzią jest o(n), a napis pojawi się 2n razy.