[Teoria złożoności][C] Oszacowanie złożoności

[LawlietDB]

Dzień dobry

Przewertowałem kilkanaście stron, ale nie do końca rozumiem jak to prawidłowo wyliczyć.

Algorytm wygląda następująco:

Kod: Zaznacz cały

        int f = 1, n, x, licznik = 0;
        printf("Podaj wartosc n: ");
        scanf("%d", &n);
        printf("Podaj wartosc x: ");
        scanf("%d", &x);
       
        while(n > 0) {
                if(n%2 == 0) {
                        x = x*x;
                        n = n/2;
                        licznik++;
                }
                else {
                        f = f*x;
                        n = n-1;
                        licznik++;
                }
        }

Mamy dwie instrukcje scan, if, else no i while. Rozumiem, że jedna z instrukcji (if/else) zostanie wykonana o 1 raz mniej, tak? Zatem jedna wykona się n razy, a druga n-1. Czy dobrze rozumuję? Jak dalej pójść tym tropem?

Z góry dziękuję za odpowiedź.

[norwimaj]

Mamy dwie instrukcje scan, if, else no i while. Rozumiem, że jedna z instrukcji (if/else) zostanie wykonana o 1 raz mniej, tak?

Nie.

Zatem jedna wykona się n razy, a druga n-1. Czy dobrze rozumuję?

Zdecydowanie nie.

Jak dalej pójść tym tropem?

Lepiej przyjrzyj się działaniu algorytmu dla konkretnych wartości \(\displaystyle{ n}\). Na przykład weź \(\displaystyle{ n=32}\) i zobacz, czy któraś z instrukcji wykona się \(\displaystyle{ 32}\) razy.

[LawlietDB]

Rozrysowałem sobie to wszystko dokładnie. Spisałem kilka wartości przy danym n otrzymany licznik. Funkcja jaka z tego powstałą jest równa "log n". Można odpowiedzieć, że szacunkiem złożoności obliczeniowej dla tego algorytmu jest O(log n)?

[norwimaj]

Tak, ten algorytm oblicza \(\displaystyle{ x^n}\) w złożoności \(\displaystyle{ O(\log n)}\), a nawet dokładnie \(\displaystyle{ \Theta(\log n)}\).