Question

Care este diferența dintre algoritmii liniari și algoritmii cu remificări

Answer 1

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