Pytanie egzaminacyjne · INF.04
int licznik = 0;
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j *= 2)
licznik++;Pytanie z zakresu egzaminu zawodowego INF.04 (Projektowanie, programowanie i testowanie aplikacji). Wybierz odpowiedź, a pokażemy poprawną i wyjaśnimy dlaczego.
Dlaczego tak
Pętla zewnętrzna wykonuje się n razy. Pętla wewnętrzna podwaja j przy każdym obrocie, więc dochodzi do n po ok. log₂ n krokach. Łącznie instrukcja licznik++ wykona się około n · log₂ n razy, czyli złożoność wynosi O(n log n). Odpowiedź O(n²) byłaby poprawna, gdyby wewnętrzna pętla zwiększała j o 1 — to najczęstszy błąd przy ocenie zagnieżdżonych pętli.
Temat: Stosuje metody rozwiązywania problemów za pomocą algorytmów
Ćwicz cały egzamin INF.04
Trenażer dobiera pytania do Twoich błędów i pilnuje powtórek. Za darmo.
Ćwicz w trenażerzeKalkulatory, materiały, pytania z forum i firmy