#181: Оценка сложности алгоритмов. Time and Space Complexity. Big O нотация.

• Видео посвящено теме вычислительной сложности, которая выражается через время исполнения и потребление памяти.  

• Эта тема важна для всех, кто устраивается в компании, включая менеджеров, системных инженеров и программистов.  

• Знания о вычислительной сложности связаны с другими областями, такими как программирование, аппаратная архитектура и проектирование систем.  

• Важно понимать, как вычисления влияют на работу программ, систем и проектов.  

• Системные инженеры и архитекторы программного продукта играют важную роль в разработке и проектировании систем для выполнения программ.  

• Системные инженеры подготавливают системы для выполнения программ, а архитекторы программного продукта устанавливают требования к системе.  

• Оценка вычислительной сложности необходима для определения того, какие вычисления могут быть выполнены машиной, а какие требуют слишком много времени и ресурсов.  

• Это важно для проектирования и построения надежных и отказоустойчивых систем.  

• Алгоритм - это метод решения задачи, представленный в виде конечного текста.  

• Алгоритм должен быть эффективным, то есть выполняться за конечное время.  

• Алгоритм оценивается по количеству операций и объему памяти, необходимых для его выполнения.  

• Линейная зависимость между количеством операций и объемом данных не всегда верна.  

• Пример: проверка четности числа в двоичной системе счисления.  

• Операция всегда одна: проверка самого наименьшего бита.  

• Пример: преобразование числа из одной системы счисления в другую.  

• Определение листа сигнификат-бита для определения четности числа.  

• Алгоритм требует ровно одну операцию проверки листа сигнификабита для определения четности числа.  

• Временная сложность алгоритма - константа, не зависит от размера входных данных.  

• Задача: найти и сложить карты одной масти по убыванию.  

• Ворст-кейс: данные уже отсортированы в обратном порядке.  

• Бест-кейс: данные уже отсортированы.  

• Эвч-кейс: данные представлены в случайном порядке.  

• Временная сложность: сумма натурального ряда.  

• Биг-о: доминирующая часть формулы для оценки сложности алгоритма.  

• Омега-нотация: минимальное количество операций для готового ответа.  

• Тета-нотация: усредненная сложность.  

• Примеры: задача проверки четности, сортировка карт, проблема странствующего агента по продаже.  

• Обсуждение сложности алгоритмов и их зависимости от входных параметров.  

• Примеры: факториал, экспоненциальная зависимость, нп- проблемы.  

• Выбор структуры данных зависит от требований к скорости, памяти и ограничений на ресурсы.  

• Примеры: массив, хэш-таблица, их зависимости и использование в различных задачах.  

• Проектирование систем должно учитывать их рост и эксплуатацию в будущем.  

• Примеры: учетные записи посетителей отеля, выбор структуры данных для хранения данных.