Урок 4: Big-O и анализ сложности

Представьте огромную телефонную книгу, в которой вы ищете одно имя: перелистывать страницу за страницей — целая вечность, но книга, упорядоченная по алфавиту, даёт куда более разумный способ. В этом уроке мы дадим такому шаблону короткое имя — Big-O — удобный способ описать, как объём работы растёт

Big-O — это просто вопрос: «если удвоить количество элементов, насколько больше станет работы?». Если вы проходите по каждому элементу один раз, удвоение элементов = удвоение работы (мы называем это O(n)). Если вы сравниваете каждый элемент с каждым, удвоение элементов = вчетверо больше работы (O(n²)). Вот и всё — короткое имя для того, как быстро растёт объём работы.

анализ сложности: Оценка объёма работы (времени) и памяти, необходимых алгоритму, как функции размера входных данных n.
Big-O: Обозначение скорости роста алгоритма в худшем случае, без учёта констант и слагаемых меньшего порядка.
линейное время: O(n): объём работы растёт прямо пропорционально размеру входных данных — один проход по каждому элементу.