Răspuns:
Un algoritm este liniar daca are complexitatea in timp polinomiala. Exemple:
\begin{lgathered}BubbleSort \rightarrow\ O(n^2)\\LinearSearch \rightarrow O(n)\\ InsertionSort \rightarrow O(n^2)\end{lgathered}BubbleSort→ O(n2)LinearSearch→O(n)InsertionSort→O(n2)
BackTracking \rightarrow O(n^k)|_{k=dimensiunea\ spatiului\ solutiilor}BackTracking→O(nk)∣k=dimensiunea spatiului solutiilor
Un algoritm este neliniar (se poate numi ramificat) daca are complexitatea in timp nonpolinomiala. Exemple:
\begin{lgathered}BinarySearch \rightarrow O(\log_2n)\\MergeSort \rightarrow O(n\cdot\log_2n)\\HeapSort \rightarrow O(n\cdot \log_2n)\\\end{lgathered}BinarySearch→O(log2n)MergeSort→O(n⋅log2n)HeapSort→O(n⋅log2n)
Algoritmii neliniari (ramificati) sunt uzual implementati prin functii recursive. Algoritmii liniari sunt uzual implementati prin bucle (for, while, do-while).
