Назовите примеры алгоритмов и структур данных с линейной, квадратичной и логарифмической сложностью. Какая сложность у поиска элемента в массиве и быстрой сортировки?

Линейный просмотр массива — O(n), попарное сравнение всех элементов — O(n²), бинарный поиск в отсортированном массиве — O(log n). Quicksort в среднем O(n log n), в худшем O(n²).

Сложность относится к операции, а не просто названию структуры. Доступ к элементу массива по индексу обычно O(1), поиск произвольного значения без индекса — O(n). В сбалансированном дереве поиск O(log n). У quicksort результат зависит от разбиения и выбора опорного элемента; средняя оценка не является гарантией худшего случая.