Какая алгоритмическая сложность поиска элемента в Array без знания индекса?

Question

Поиск элемента в Array без индекса — это линейный проход (linear search), его сложность O(n), где n — число элементов.

YeaHub · Accepted Answer

Линейный поиск (Linear Search):Идём по элементам последовательно, пока не найдём совпадение.В худшем случае проверим все элементы.Оценка сложности:Лучший случай: O(1), если нужный элемент находится первым.Средний и худший: O(n), потому что может потребоваться просмотр всех элементов.Пример:let a = [3, 7, 2, 9]
for item in a {
    	if item == 9 {
        	print("Найдено") // после 4 итераций
    	}
}Альтернативы:Если нужен быстрый поиск, лучше использовать Set или Dictionary (O(1) в среднем).Для отсортированного массива можно применить бинарный поиск (O(log n)) через Array.binarySearch или вручную.