Sprawdź się
Czy kwadratowa złożoność obliczeniowa jest złożonością wielomianową?
- tak
- nie
Spośród podanych niżej symboli wybierz ten, który oznacza notację "duże O".
Materiał źródłowy do ćwiczeń nr 4–5
- 1. zestaw danych:
- n: 1
- √n: 1
- (n^4)/2: 0,5
- 3(n^3): 3
- 2. zestaw danych:
- n: 25
- √n: 5
- (n^4)/2: 195312,5
- 3(n^3): 46875
- 3. zestaw danych:
- n: 100
- √n: 10
- (n^4)/2: 50000000
- 3(n^3): 3000000
Wskaż, który ze składników funkcji ma najmniejszy wpływ na jej tempo wzrostu.
Połącz w pary funkcje opisujące dokładną liczbę wykonywanych operacji z odpowiadającą im złożonością obliczeniową.
<span aria-label="O nawias n zamknięcie nawiasu" role="math"><math><mi>O</mi><mo>(</mo><mi>n</mi><mo>)</mo></math></span>, <span aria-label="O nawias n indeks górny, dwa, zamknięcie nawiasu" role="math"><math><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></math></span>, <span aria-label="O nawias logarytm z n zamknięcie nawiasu" role="math"><math><mi>O</mi><mo>(</mo><mi>log</mi><mo> </mo><mi>n</mi><mo>)</mo></math></span>, <span aria-label="O nawias jeden zamknięcie nawiasu" role="math"><math><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></math></span>, <span aria-label="O nawias n logarytm z n zamknięcie nawiasu" role="math"><math><mi>O</mi><mo>(</mo><mi>n</mi><mo> </mo><mi>log</mi><mo> </mo><mi>n</mi><mo>)</mo></math></span>
Programy z kwadratową złożonością czasową działają 1. małym, 2. należy to zrobić, 3. nie należy tego robić, 4. szybciej, 5. wolniej, 6. dużym od tych z liniowo-logarytmiczną.
Jeżeli jesteśmy w stanie zmniejszyć złożoność obliczeniową algorytmu kosztem jego poprawności to 1. małym, 2. należy to zrobić, 3. nie należy tego robić, 4. szybciej, 5. wolniej, 6. dużym.
Wstaw brakujące wyrażenia tak, aby treść poniższych zdań była prawdziwa.
dużym, wolniej, należy to zrobić, małym, szybciej, nie należy tego robić
Złożoność obliczeniowa algorytmu w .............................................. stopniu decyduje o jego użyteczności.
Programy z kwadratową złożonością czasową działają .............................................. od tych z liniowo-logarytmiczną.
Jeżeli jesteśmy w stanie zmniejszyć złożoność obliczeniową algorytmu kosztem jego poprawności to ...............................................
Zapoznaj się z wykresami przedstawiającymi zależność złożoności obliczeniowej od liczby danych. Legenda do wykresów została sporządzona błędnie. Opisz, w jaki sposób należy ją zmienić, by poprawnie opisywała, do jakiego typu złożoności odnosi się dana wartość na wykresie.
- 1. zestaw danych:
- n: 3
- A: 1
- B: 9
- C: 3
- D: 8
- 2. zestaw danych:
- n: 5
- A: 1
- B: 25
- C: 5
- D: 32
- 3. zestaw danych:
- n: 10
- A: 1
- B: 100
- C: 10
- D: 1024