Złożoność O duże

Złożoność czasowa

Określa, jak czas wykonania algorytmu zmienia się w zależności od wielkości wejścia.

O(n)

Oznacza, że czas działania algorytmu rośnie liniowo wraz z rozmiarem danych wejściowych.

Prawda czy fałsz: O(log n) jest szybsze niż O(n)

Prawda, ponieważ O(log n) rośnie wolniej niż O(n).

Różnica między O(n) a O(n²)

O(n) rośnie liniowo, O(n²) rośnie kwadratowo, co znacznie zwiększa czas działania dla większych n.

O(1)

Złożoność stała, niezależna od rozmiaru danych wejściowych.

Algorytm sortowania bąbelkowego

Ma złożoność O(n²) w najgorszym przypadku, przez co jest mniej efektywny dla dużych zbiorów danych.

Uzupełnij zdanie: Złożoność O(n log n) często występuje w ___

algorytmach sortujących jak sortowanie szybkie i sortowanie przez scalanie.

Który algorytm ma złożoność O(n log n)?

Sortowanie przez scalanie (merge sort) jest przykładem algorytmu z tą złożonością.

Co to jest notacja asymptotyczna?

Metoda analizy wydajności algorytmu, używająca oznaczeń O, Θ i Ω do klasyfikacji złożoności.

Prawda czy fałsz: O(n!) jest bardziej efektywne niż O(2^n)

Fałsz, ponieważ O(n!) rośnie znacznie szybciej niż O(2^n).

Złożoność O(k)

Jest złożonością stałą, gdzie k to dowolna stała liczba. Nie zmienia się w zależności od n.

Jakie są główne typy złożoności?

Czasowa i pamięciowa to dwa główne typy, które pomagają w ocenie algorytmu.

Złożoność pamięciowa

Mierzy, ile pamięci potrzebuje algorytm w stosunku do rozmiaru danych wejściowych.

O(n^3)

Oznacza, że czas działania algorytmu wzrasta sześciennie w zależności od wielkości danych.

Porównanie O(n) i O(1)

O(n) rośnie w zależności od n, podczas gdy O(1) pozostaje stałe, co czyni O(1) bardziej efektywnym.

Co to jest złożoność eksponencjalna?

Złożoność O(2^n) jest przykładem złożoności eksponencjalnej, gdzie czas działania rośnie bardzo szybko.