📌 Оценка алгоритмов для самых маленьких // Swift

swift
ios

#1

Всем привет! Я написал небольшую статью, возможно будет интересно:


#2

Да уж… для самых маленьких. Но спасибо, интересно думаю будет скоро )))


#3

Сложно показалось? Завайте вопросы)
Это такой самый минимум, без которого сложно погружаться в алгоритмы.
Можете попробовать посмотреть лекцию из ШАД)


#4

Спасибо за статью! Если есть что почитать присылай.


#5

Статья для самых маленьких, а вычислений нету. Так как же вычисляется сложность алгоритмов?


#6

Пожалуйста! Следующая статья скорее всего будет про решение задач на примере соревнования или из сервиса по типу https://www.hackerrank.com. Но это не точно)


#7

Отличный вопрос) Думаю вы правы, у меня не вышло научить оценивать)
На самом деле я старался объяснить оценку на примере операций массива.

Если нам требуется перебрать весь массив (порядка n элементов - это и есть размер входа), то такой алгоритм будет оцениваться как O(n). О большое от n или линейное время работы. Важно заметить, что константы не учитываются. То есть если нам надо будет просмотреть всегда половину входа, то всё равно будет O(n). Это называется скрытая константа.

Константное время работы алгоритма или O(1) означает, что размер входа не важен. Алгоритм всегда будет делать определенное количество действий.

Квадратичное время - это как правило цикл в цикле. Логарифмическое - это бинарный поиск или деревья) А дальше уже идут различные комбинации этих асимптотик.

Также важно заметить, что если у нас сложный алгоритм и там сразу линейный перебор, и квадратичный, и логарифмический, то будет учитываться только самая быстро растущая часть. То есть в данном примере - квадратичная асимптотика.

Постарался коротко написать. Если вам стало понятно, то я очень рад) но это более сложный материал и я решил не включать его в статью.
Но я рассказывал это на докладе)


#8

Спасибо, уже немного лучше.


#9

Отлично) Пожалуйста)