Które z wymienionych oznaczeń wskazuje na liniową złożoność algorytmu?
Złożoność O(n) oznacza liniową zależność czasu wykonania algorytmu od rozmiaru danych wejściowych. Oznacza to, że dla każdego dodatkowego elementu algorytm wykonuje jedną dodatkową operację. Algorytmy liniowe są jednymi z najczęściej stosowanych w praktyce, ponieważ oferują dobrą równowagę między szybkością a złożonością implementacji. Przykłady algorytmów o złożoności O(n) to przeszukiwanie liniowe (Linear Search), sumowanie elementów tablicy oraz niektóre algorytmy sortowania, takie jak Counting Sort dla określonych warunków. Liniowa złożoność czyni te algorytmy bardzo efektywnymi przy przetwarzaniu dużych zbiorów danych.
O(1) oznacza stałą złożoność czasową, co oznacza, że algorytm wykonuje tę samą liczbę operacji niezależnie od rozmiaru danych wejściowych – jest to typowe dla operacji na haszmapach lub tablicach asocjacyjnych. O(n²) oznacza kwadratową złożoność algorytmu, gdzie liczba operacji rośnie proporcjonalnie do kwadratu liczby elementów – jest to charakterystyczne dla algorytmów takich jak Bubble Sort czy Insertion Sort. O(log n) wskazuje na logarytmiczną złożoność i jest typowe dla algorytmów wyszukiwania binarnego (Binary Search) i niektórych algorytmów operujących na drzewach.