Podgląd pytania

Pojedyncze pytanie z bazy egzaminacyjnej wraz z poprawną odpowiedzią i wyjaśnieniem. Przeglądaj bez logowania, a gdy będziesz gotowy, sprawdź się w pełnym teście próbnym.

ID: 2642 Algorytmy Średnie
INF.04

Źródło: Arkusze CKE

Które określenie najlepiej opisuje złożoność obliczeniową algorytmu quicksort?

Warianty odpowiedzi

  1. A

    jest różna w zależności od wyboru elementu rozdzielającego
  2. B

    jest wyższa niż złożoność sortowania bąbelkowego
  3. C

    jest zawsze niższa niż złożoność każdego innego algorytmu sortowania
  4. D

    jest wyższa niż O(n2).

Wyjaśnienie

Szybkość działania QuickSorta zależy bezpośrednio od tego, jak trafnie wybierzemy tak zwany pivot, czyli element podziału.

Jeśli mamy szczęście i pivot dzieli dane na dwie równe części, algorytm działa bardzo szybko, osiągając złożoność O(n log n).

Problem pojawia się, gdy jako pivot stale trafia się najmniejszy lub największy element, na przykład w posortowanej już tablicy. Wtedy algorytm spada do fatalnej złożoności O(n^2), bo wykonuje mnóstwo zbędnych porównań.

Sprawdź się w praktyce

Rozwiąż pełny test próbny INF.04 albo wylosuj pojedyncze pytanie na szybką powtórkę.

Test próbny INF.04 Jedno pytanie Własny test

Podobne pytania — Algorytmy

Wszystkie pytania INF.04