Вся сложность алгоритмов за 11 минут - основы программирования
содержание видео
1. Временная сложность: Временная сложность алгоритма относится к количеству времени, необходимому для решения задачи при увеличении размера входных данных. Алгоритмы с более высокой временной сложностью обычно считаются более сложными в решении, чем те, у которых временная сложность ниже.
2. Пространственная сложность: Пространственная сложность алгоритма относится к объему памяти, необходимому для решения задачи при увеличении размера входных данных. Алгоритмы с более высокой пространственной сложностью могут быть более сложны в реализации или оптимизации, чем те, у которых пространственная сложность ниже.
3. Область применения: Сложность алгоритма также может зависеть от области применения, для которой он разработан. Некоторые задачи могут иметь врожденную сложность, которую нельзя снизить с помощью алгоритмических оптимизаций.
4. Характеристики входных данных: Характеристики входных данных могут также влиять на сложность алгоритма. Некоторые алгоритмы могут быть более сложны в реализации или оптимизации для определенных типов входных данных, таких как большие числа, разреженные данные или данные с множеством повторяющихся образцов.
5. Детали реализации: Детали реализации алгоритма, такие как выбор структур данных или языка программирования, также могут повлиять на его сложность.
В целом, определение сложности алгоритма может быть сложным процессом, требующим тщательного анализа и учета многих факторов.
Big O - это математическая нотация, используемая для определения временной сложности алгоритма, то есть описания того, как быстро работает алгоритм при увеличении размера входных данных.
Она указывает на асимптотическую верхнюю границу времени выполнения алгоритма и позволяет определить, как быстро будет расти время выполнения алгоритма при увеличении размера входных данных.
Обычно Big O записывается в виде O(f(n, где f(n) - функция, описывающая количество операций, которые выполняет алгоритм при обработке n элементов входных данных. Например, если алгоритм имеет временную сложность O(n, то это означает, что время выполнения алгоритма пропорционально размеру входных данных.
Big O используется для сравнения и анализа различных алгоритмов и помогает выбирать наиболее оптимальный алгоритм для решения конкретной задачи. Она также позволяет оценить, насколько эффективно можно оптимизировать алгоритм при работе с большими объемами данных.
Дата: 2023-03-12
Похожие видео
Комментарии и отзывы: 19
Alexander
Спасибо за видео! Полезно не забывать об этой теме, хоть в лично в моей практике уже давно достаточно редко приходится упарываться в жесткую алгоритмику. Но вот чем мне всегда О-нотация не нравилась, так как раз своей грубостью. Часто знать о двух разных алгоритмах, что они просто O(N) (или любая другая функция) - это ничего не знать. Представьте себе абстрактную ситуацию, что выбираете алгоритм для своей задачи из магазина, и в характеристиках у обоих обозначена сложность O(N. Но один (1) из них выполняет по факту в среднем N/2 операций. А другой (2) всегда выполняет 1000N. Хоть они оба и O(N, первый будет значительно предпочтительнее второго. Во-первых потому, что N для него - действительно максимум. Во-вторых, что в большой части случаев он будет завершаться, выполнив меньше N операций.
Но в чем же заключается дополнительная проблема алгоритма (2, про который известно, что он O(N, но неизвестно, что фактически он всегда выполняет 1000N операций, помимо того, что он очевидно менее оптимален, чем первый? А проблема как раз в том, что просто сравнение разных сложностей в O-нотации не совсем корректно. Вот теперь представьте, что есть еще алгоритм (3, решающий эту же задачу, но имеющий сложность O(N2. Он же сложнее, чем O(N, так? Так, да не так. Если просто взглянуть на эти две функции: 1000N и N2, легко увидеть, что тот более быстрый алгоритм O(N) (который фактически 1000N, но коэффициент мы пренебрежительно отбросили) будет по факту выполняться дольше, чем N2 для N < 1000. А теперь представьте, что сама наша исходная задача и не предполагает работать с N, большими 1000. В этом случае нам было бы выгоднее взять этот третий алгоритм, если выбирать только из этих двух. А теперь представьте, что оценка этого третьего алгоритма тоже сделана слишком грубо, и по факту точнее было бы говорить об (N/10)2 - это по-прежнему O(N2, но сравнивая его с (2, он будет быстрее уже не только при N < 1000, а при N < 100000.
ответить
Спасибо за видео! Полезно не забывать об этой теме, хоть в лично в моей практике уже давно достаточно редко приходится упарываться в жесткую алгоритмику. Но вот чем мне всегда О-нотация не нравилась, так как раз своей грубостью. Часто знать о двух разных алгоритмах, что они просто O(N) (или любая другая функция) - это ничего не знать. Представьте себе абстрактную ситуацию, что выбираете алгоритм для своей задачи из магазина, и в характеристиках у обоих обозначена сложность O(N. Но один (1) из них выполняет по факту в среднем N/2 операций. А другой (2) всегда выполняет 1000N. Хоть они оба и O(N, первый будет значительно предпочтительнее второго. Во-первых потому, что N для него - действительно максимум. Во-вторых, что в большой части случаев он будет завершаться, выполнив меньше N операций.
Но в чем же заключается дополнительная проблема алгоритма (2, про который известно, что он O(N, но неизвестно, что фактически он всегда выполняет 1000N операций, помимо того, что он очевидно менее оптимален, чем первый? А проблема как раз в том, что просто сравнение разных сложностей в O-нотации не совсем корректно. Вот теперь представьте, что есть еще алгоритм (3, решающий эту же задачу, но имеющий сложность O(N2. Он же сложнее, чем O(N, так? Так, да не так. Если просто взглянуть на эти две функции: 1000N и N2, легко увидеть, что тот более быстрый алгоритм O(N) (который фактически 1000N, но коэффициент мы пренебрежительно отбросили) будет по факту выполняться дольше, чем N2 для N < 1000. А теперь представьте, что сама наша исходная задача и не предполагает работать с N, большими 1000. В этом случае нам было бы выгоднее взять этот третий алгоритм, если выбирать только из этих двух. А теперь представьте, что оценка этого третьего алгоритма тоже сделана слишком грубо, и по факту точнее было бы говорить об (N/10)2 - это по-прежнему O(N2, но сравнивая его с (2, он будет быстрее уже не только при N < 1000, а при N < 100000.
ответить
Yan
Отсюда сразу можно понять, что такое интеллект, зачем он нужен, и чем занимается.
Интеллект - это оптимизирующая машина. Которая занимается тем, что переводит задачи NP сложности и полноты (факториальные и полиномиальные по бигО) - в задачи P сложности и полноты (полиномиальные, логарифмические и константные по бигО.
Как он это делает?
Увы, это не известно, и не доказано до сих пор в общем виде (а кто докажет - получит премию института Клэя, в один мегабакс.
Но, концептуально, такую схему представить таки можно.
Интеллект, в хаотических, ничем не связанных, данных - ищет скрытые взаимосвязи и закономерности.
Опираясь на ранее полученные знания, проверяя индуктивные гипотезы, и фильтруя их опытом, он выстраивает, наконец, дедуктивную стратегию.
И доводит её, стратегию, до интуитивного навыка, до совершенного, отлаженного автоматизма, до готовой и надёжной технологии.
И, тем самым, понижая их, данных, колмогоровскую энтропию - до минимума, работая, как тепловой насос.
(А о ней, о колмогоровской энтропии, и шла речь в ролике, под никнеймом бигО.
Иллюстрации см. на рисунке (пост в ВК.
ответить
Отсюда сразу можно понять, что такое интеллект, зачем он нужен, и чем занимается.
Интеллект - это оптимизирующая машина. Которая занимается тем, что переводит задачи NP сложности и полноты (факториальные и полиномиальные по бигО) - в задачи P сложности и полноты (полиномиальные, логарифмические и константные по бигО.
Как он это делает?
Увы, это не известно, и не доказано до сих пор в общем виде (а кто докажет - получит премию института Клэя, в один мегабакс.
Но, концептуально, такую схему представить таки можно.
Интеллект, в хаотических, ничем не связанных, данных - ищет скрытые взаимосвязи и закономерности.
Опираясь на ранее полученные знания, проверяя индуктивные гипотезы, и фильтруя их опытом, он выстраивает, наконец, дедуктивную стратегию.
И доводит её, стратегию, до интуитивного навыка, до совершенного, отлаженного автоматизма, до готовой и надёжной технологии.
И, тем самым, понижая их, данных, колмогоровскую энтропию - до минимума, работая, как тепловой насос.
(А о ней, о колмогоровской энтропии, и шла речь в ролике, под никнеймом бигО.
Иллюстрации см. на рисунке (пост в ВК.
ответить
solacerxt
10: 20 очень странный вывод без каких-либо оговорок. Естественно, сложность по памяти не рекурсивной функции может быть не константной. Пример: в функции создаёшь массив из n элементов. Сложность O(n. Расход памяти нужно считать не только на стеке, но и в куче (хотя память можно также выделять на стеке во многих языках программирования.
Автор видео вроде бы пытается показать многогранность оценки сложности алгоритмов разбором разных случаев, но обобщения, подобные указанному выше, и замечания вроде 5: 56 производят о видео впечатление шпаргалки для школьника, которому нужно решить домашку и забыть. Автор даже не дал определение этой самой О-нотации, а лишь указал на некоторые свойства по ходу видео. А ведь если бы это сделано вместе с разбором нескольких примеров (не выводя оценку эмпирически, вроде посчитаем количество вершин в дереве для 3, 4, 5 и заметим зависимость, а потом обобщим без доказательства, то за те же 11 минут зрителю можно было бы дать куда большее понимание данной темы.
ответить
10: 20 очень странный вывод без каких-либо оговорок. Естественно, сложность по памяти не рекурсивной функции может быть не константной. Пример: в функции создаёшь массив из n элементов. Сложность O(n. Расход памяти нужно считать не только на стеке, но и в куче (хотя память можно также выделять на стеке во многих языках программирования.
Автор видео вроде бы пытается показать многогранность оценки сложности алгоритмов разбором разных случаев, но обобщения, подобные указанному выше, и замечания вроде 5: 56 производят о видео впечатление шпаргалки для школьника, которому нужно решить домашку и забыть. Автор даже не дал определение этой самой О-нотации, а лишь указал на некоторые свойства по ходу видео. А ведь если бы это сделано вместе с разбором нескольких примеров (не выводя оценку эмпирически, вроде посчитаем количество вершин в дереве для 3, 4, 5 и заметим зависимость, а потом обобщим без доказательства, то за те же 11 минут зрителю можно было бы дать куда большее понимание данной темы.
ответить
Олег
9 Я есмь дверь: кто войдет Мною, тот спасется, и войдет, и выйдет, и пажить найдет.
10 Вор приходит только для того, чтобы украсть, убить и погубить. Я пришел для того, чтобы имели жизнь и имели с избытком.
11 Я есмь пастырь добрый: пастырь добрый полагает жизнь свою за овец.
12 А наемник, не пастырь, которому овцы не свои, видит приходящего волка, и оставляет овец, и бежит; и волк расхищает овец, и разгоняет их.
13 А наемник бежит, потому что наемник, и нерадит об овцах.
14 Я есмь пастырь добрый; и знаю Моих, и Мои знают Меня.
15 Как Отец знает Меня, [так] и Я знаю Отца; и жизнь Мою полагаю за овец.
16 Есть у Меня и другие овцы, которые не сего двора, и тех надлежит Мне привести: и они услышат голос Мой, и будет одно стадо и один Пастырь.
17 Потому любит Меня Отец, что Я отдаю жизнь Мою, чтобы опять принять ее.
18 Никто не отнимает ее у Меня, но Я Сам отдаю ее. Имею власть отдать ее и власть имею опять принять ее. Сию заповедь получил Я от Отца Моего.
(Иоан. 10: 9-18)
ответить
9 Я есмь дверь: кто войдет Мною, тот спасется, и войдет, и выйдет, и пажить найдет.
10 Вор приходит только для того, чтобы украсть, убить и погубить. Я пришел для того, чтобы имели жизнь и имели с избытком.
11 Я есмь пастырь добрый: пастырь добрый полагает жизнь свою за овец.
12 А наемник, не пастырь, которому овцы не свои, видит приходящего волка, и оставляет овец, и бежит; и волк расхищает овец, и разгоняет их.
13 А наемник бежит, потому что наемник, и нерадит об овцах.
14 Я есмь пастырь добрый; и знаю Моих, и Мои знают Меня.
15 Как Отец знает Меня, [так] и Я знаю Отца; и жизнь Мою полагаю за овец.
16 Есть у Меня и другие овцы, которые не сего двора, и тех надлежит Мне привести: и они услышат голос Мой, и будет одно стадо и один Пастырь.
17 Потому любит Меня Отец, что Я отдаю жизнь Мою, чтобы опять принять ее.
18 Никто не отнимает ее у Меня, но Я Сам отдаю ее. Имею власть отдать ее и власть имею опять принять ее. Сию заповедь получил Я от Отца Моего.
(Иоан. 10: 9-18)
ответить
Вася
0: 44 O(N log N) на графике не выглядит как логарифм, и загибается вверх а не вниз
На большой дистанции линейно-логарифмическая сложность - хуже линейной, что у вас обозначено
С графиком на первой минуте может показаться, что линейно-логарифмическая когда-то догонит линейную, но это не так - эти две функции можно считать полностью расходящимися
Так же не полностью раскрыта тема коэффициентов, когда сложность алгоритма не получится оценить двухмерной асимптотикой
Там сложность оценивается уже пространственно
Я не знаю работает ли это для памяти, не сталкивался
Но не удивлюсь если такие пространственные коэффициенты применимы и для памяти
ответить
0: 44 O(N log N) на графике не выглядит как логарифм, и загибается вверх а не вниз
На большой дистанции линейно-логарифмическая сложность - хуже линейной, что у вас обозначено
С графиком на первой минуте может показаться, что линейно-логарифмическая когда-то догонит линейную, но это не так - эти две функции можно считать полностью расходящимися
Так же не полностью раскрыта тема коэффициентов, когда сложность алгоритма не получится оценить двухмерной асимптотикой
Там сложность оценивается уже пространственно
Я не знаю работает ли это для памяти, не сталкивался
Но не удивлюсь если такие пространственные коэффициенты применимы и для памяти
ответить
Razor23
Не являюсь спецом в этой теме, не смотря на то, что довольно часто слышал на собеседованиях (и больше особо нигде. Во многом потому, что, по-моему, это оценка абсолютно оторвана от реальности. Начиная от отбрасывания констант (любых, и заканчивая тем, что, в реальном мире, всё всегда работает в определённом диапазоне, а не растёт до бесконечности и считать как бы надо конкретно какой алгоритм будет хорошо работать на ваших данных. а не вот так вот, в вакууме.
Знающие люди, отзовитесь, где эта нотация реально показывает свою пригодность и полезность?
ответить
Не являюсь спецом в этой теме, не смотря на то, что довольно часто слышал на собеседованиях (и больше особо нигде. Во многом потому, что, по-моему, это оценка абсолютно оторвана от реальности. Начиная от отбрасывания констант (любых, и заканчивая тем, что, в реальном мире, всё всегда работает в определённом диапазоне, а не растёт до бесконечности и считать как бы надо конкретно какой алгоритм будет хорошо работать на ваших данных. а не вот так вот, в вакууме.
Знающие люди, отзовитесь, где эта нотация реально показывает свою пригодность и полезность?
ответить
ALLiNi
Два момента на 6: 30 по коду меня напрягли:
1. Разве нет возможности взять последний элемент массива (который упорядочен) по другому? Зачем брать длину и вычитать единицу?
2. Расчёт mid. Зачем два раза использовать left и использовать две операции + и -, когда можно просто вычислить как: (left+right)/2? Поиск работает также, при этом математических операций меньше. К тому же, разве нет системной функции вычисления среднего значения или она дольше выполняется?
P. S. Заранее извиняюсь за неточность термином, но думаю меня правильно поймут.
ответить
Два момента на 6: 30 по коду меня напрягли:
1. Разве нет возможности взять последний элемент массива (который упорядочен) по другому? Зачем брать длину и вычитать единицу?
2. Расчёт mid. Зачем два раза использовать left и использовать две операции + и -, когда можно просто вычислить как: (left+right)/2? Поиск работает также, при этом математических операций меньше. К тому же, разве нет системной функции вычисления среднего значения или она дольше выполняется?
P. S. Заранее извиняюсь за неточность термином, но думаю меня правильно поймут.
ответить
Кирилл
Спасибо за видео! Доходчиво и с картинками! :D
Кстати, сейчас друг написал, попросил функцию посмотреть (упрощенно - собирает символы по паттерну и печатает их) - показал скриншот из видео, прокомментировав, что у него по памяти получается O(N) - делал конкатенацию строки. Друг понял и пошел оптимизировать! Скинул ему ссылку на видео)
А что за музыка в рекламе на фоне с 2: 22 / в конце видео используется)
ответить
Спасибо за видео! Доходчиво и с картинками! :D
Кстати, сейчас друг написал, попросил функцию посмотреть (упрощенно - собирает символы по паттерну и печатает их) - показал скриншот из видео, прокомментировав, что у него по памяти получается O(N) - делал конкатенацию строки. Друг понял и пошел оптимизировать! Скинул ему ссылку на видео)
А что за музыка в рекламе на фоне с 2: 22 / в конце видео используется)
ответить
TheAcckiySatana
Я таки уточню, вы оцениваете сложность алгоритма по процессорному времени, и по затраченной памяти? Однако из ваших примеров, так же можно выйти из цикла по нахождению нужного результата. В бизнесе, на мой взгляд, давно не смотрят на алгоритм так низко, смотрят, как сделать максимально быстро и на более высшем уровне. Нужен результат вчера, а не разбор на время одного ядра ЦП.
ответить
Я таки уточню, вы оцениваете сложность алгоритма по процессорному времени, и по затраченной памяти? Однако из ваших примеров, так же можно выйти из цикла по нахождению нужного результата. В бизнесе, на мой взгляд, давно не смотрят на алгоритм так низко, смотрят, как сделать максимально быстро и на более высшем уровне. Нужен результат вчера, а не разбор на время одного ядра ЦП.
ответить
Аккаунт
как то раз я посмотрел подобный видос и меня это только больше запутало. Без формальных определений нельзя рассказывать примеры сложностей и то, как их считать. Видео больше путает, чем разъясняет(если вы не знали тему раньше, а если знали то видео просто бесполезно. Лучше загуглите эту тему, видос не советую, по крайней мере не советую смотреть его первым по этой теме.
ответить
как то раз я посмотрел подобный видос и меня это только больше запутало. Без формальных определений нельзя рассказывать примеры сложностей и то, как их считать. Видео больше путает, чем разъясняет(если вы не знали тему раньше, а если знали то видео просто бесполезно. Лучше загуглите эту тему, видос не советую, по крайней мере не советую смотреть его первым по этой теме.
ответить
Sergei
окей гугл, тро есть Алек. Я могу работать с переменными, знаю что есть кортежи, списки, инт 32, инт 64, могу запустить цикл FOR LOOP и do loop, do while. хелло ворд тоже могу вывести. но далше - блин как и куда. дальше сразу до фига и не поятно. как вот из всего этотго запилить свой Redalt 1, railroady tycoon 2, simcity 2?
ответить
окей гугл, тро есть Алек. Я могу работать с переменными, знаю что есть кортежи, списки, инт 32, инт 64, могу запустить цикл FOR LOOP и do loop, do while. хелло ворд тоже могу вывести. но далше - блин как и куда. дальше сразу до фига и не поятно. как вот из всего этотго запилить свой Redalt 1, railroady tycoon 2, simcity 2?
ответить
Никита
Видео скорее больше запутывает без формальных определений. Также хотелось бы услышать про тета- и омега- нотации.
Советую почитать соответствующую главу книги Томаса Кормена Алгоритмы. Построение и анализ.
ответить
Видео скорее больше запутывает без формальных определений. Также хотелось бы услышать про тета- и омега- нотации.
Советую почитать соответствующую главу книги Томаса Кормена Алгоритмы. Построение и анализ.
ответить
Max
1: 48 такое ощущение, что здесь пару реплик на монтаже потеряли. А то был просто линейный перебор, ВНЕЗАПНО превратился в перебор с хитровывернутым условием и надо работу своего алгоритма хоть немного представлять.
ответить
1: 48 такое ощущение, что здесь пару реплик на монтаже потеряли. А то был просто линейный перебор, ВНЕЗАПНО превратился в перебор с хитровывернутым условием и надо работу своего алгоритма хоть немного представлять.
ответить
Vladislav
Невероятно актуально, каждое видео очень помогает разобраться в темах, которые учу самостоятельно, потому что всё крайне наглядно и понятно, всё еще с нетерпением жду продолжение цикла по ассемблеру)
ответить
Невероятно актуально, каждое видео очень помогает разобраться в темах, которые учу самостоятельно, потому что всё крайне наглядно и понятно, всё еще с нетерпением жду продолжение цикла по ассемблеру)
ответить
Павел
Мне одному кажется, что видосы у Алека в продакшн с ускоренным воспроизведение выходят? Инфа нужная и полезная, но на такой скорости что-то усвоить не представляется возможным)
ответить
Мне одному кажется, что видосы у Алека в продакшн с ускоренным воспроизведение выходят? Инфа нужная и полезная, но на такой скорости что-то усвоить не представляется возможным)
ответить
Иоанн
Предлагаю сделать видео про деревья(в частности бинарные, балансировку деревьев и всё вот это. Как будто не так много контента на эту тему на ру ютубе, либо я ошибаюсь.
ответить
Предлагаю сделать видео про деревья(в частности бинарные, балансировку деревьев и всё вот это. Как будто не так много контента на эту тему на ру ютубе, либо я ошибаюсь.
ответить
Ivan
4: 51 - позволю заметить что мы считаем не то что они будут одинаковые, а то что они будут расти одинаково (по времени или памяти) при изменении количества входных данных
ответить
4: 51 - позволю заметить что мы считаем не то что они будут одинаковые, а то что они будут расти одинаково (по времени или памяти) при изменении количества входных данных
ответить
XMAHZ
При нескольких переменных N и K допустим, скоростью алгоритма является максимальная скорость или худшая, поэтому если N больше K тогда скорость O(N) и наоборот
ответить
При нескольких переменных N и K допустим, скоростью алгоритма является максимальная скорость или худшая, поэтому если N больше K тогда скорость O(N) и наоборот
ответить
Jka
Почему рассматривается только О-большое, и еще надо было упомянуть о сложности в лучшем случае, на примере отсортированного и не отсортированного массива
ответить
Почему рассматривается только О-большое, и еще надо было упомянуть о сложности в лучшем случае, на примере отсортированного и не отсортированного массива
ответить
Добавить отзыв, комментарий
Другие видео канала
1:10
1:23
1:17
0:57
