Введение в анализ алгоритмов

(12 оценок)
Языки программирования
00:44
29 ноября 2022 г.
Наставник помогает с обучением
Бесплатно

Андрей Резанов

Инженер-программист с опытом работы в компаниях: Rambler&Co, МТС, FB.
О КУРСЕ

Цель курса - дать необходимые знания по анализу алгоритмов для программистов, которые готовятся к прохождению технического собеседования. В курсе затронуты темы: масштабируемый и качественный код, определение "О" большого, правила и примеры расчета "О" большого.

КОМУ ПОДОЙДЕТ КУРС

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


Добро пожаловать в мой курс! = )


Название Дата/Время Длительность
Введение в анализ алгоритмов 8 февраля 2023 г. в  Минут(ы)
Настройка среды разработки
Вступление в анализ алгоритмов
Что такое хороший код?
Какое "О" большое?
О(1)
Расчет "О" Большого

Правило 1

Правило 2
Правило 3
O(n^2)
Правило 4

О Большое


O(1) Константное время - нет циклов

O(logN) Логарифмическое время - обычно в алгоритмах поиска (двоичный поиск)

O(n) Линейное время - циклы for / while по n элементам

O(n*logN) - обычно в операциях сортировки

O(n^2) Квадратичное время - вложенные циклы

O(2^n) Экспоненциальное время - рекурсивные алгоритмы, которые решают задачу размера N

O(n!) Факториал - добавляем цикл для каждого элемента


Что может влиять на временную сложность?

Операции (+, -, *, /)

Сравнения (<, >, ==)

Циклы (for, while)

Вызов внешних функций - function()


Правила

Рассматриваем худший сценарийОтбрасываем константыИспользуем разные обозначения для разных переменныхОтбрасываем младшие члены


Помнить!

а. Обход половины коллекции - все равно O(n)

б. Две отдельные коллекции - O(n + m)


Что может влиять на пространственную сложность?

Переменные

Структуры данных

Вызовы функций

Выделение памяти (allocation)

Зачем нужно "О" Большое?
Пожалуйста, войдите в свою учетную запись, чтобы оставить комментарий.
  • Alexander Vagin (Студент) Интересно, спасибо
  • Илюша Фомин (Студент) Спасибо большое, хороший материал!
  • Lev Ivanov (Студент) Добрый день. Спасибо большое. В целом мне понравилось как объяснено все по поводу большого О, но хотелось бы еще услышать что-то про классические алгоритмы и структуры данных
  • Sergey Frolov (Студент) Спасибо, удалось наконец-то понять эту концепцию!
  • Kirill S (Студент) Отличный курс. Автор простым языком, доносит сложные вещи, это очень много стоит.
  • Dima Zukerman (Студент) Хотелось бы увидеть больше контента в курсе, добавить видео по алгоритмам и структурам данных
  • Arseniy Khech (Студент) Андрей, спасибо вам большое! Тема вводная, но объясняется легко и понятно. Лайк ❤️
  • Y M (Студент) Отличный курс, все очень понятно изложено, с вниманием к деталям и слушателю. Видно, что автор отлично разбирается в теме, материал воспринимается легко и интересно. Спасибо!
  • Alexander Kukharev (Студент) Хороший курс, жду продолжения
  • Kate Misureva (Студент) Спасибо большое за курс, очень полезно! Жду еще)
  • Ещё