Как выучить нотацию big o

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

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

В этом модуле вы узнаете, что программы, основанные на эффективных алгоритмах, могут решать одну и ту же задачу в миллиарды раз быстрее, чем программы, основанные на наивных алгоритмах. Вы узнаете, как оценить время работы и память алгоритма, даже не реализуя его. Вооружившись этими знаниями, вы сможете сравнивать различные алгоритмы, выбирать наиболее эффективные из них и, наконец, реализовывать их в виде наших задач по программированию!

Преподаватели

Нил Родс

Дэниел М Кейн

Майкл Левин

Павел Певзнер

Александр С. Куликов

Текст видео

Привет всем. С возвращением. Сегодня мы поговорим о нотации Big-O, которая является специфической, своего рода асимптотической нотацией, которую мы будем использовать здесь чаще всего. Итак, идея заключается в том, что мы собираемся представить значение нотации Big-O и описать некоторые ее преимущества и недостатки. Итак, начнем с определения. Идея заключается в том, что нам нужно что-то, что заботится о том, что происходит, когда входные данные становятся очень большими, и вроде как заботится только о вещах до констант. Поэтому мы собираемся придумать определение. Если у вас есть две функции, f и g. g(n) – это Big-O от g(n). Если есть две константы, большая N и маленькая c, такие, что для всех n, по крайней мере, N. f(n) – это, по крайней мере, c*g(n). И это означает, что по крайней мере для достаточно больших входов f ограничена сверху некоторым постоянным кратным g. Что действительно является своего рода идеей, которую мы имели раньше. Теперь, например, 3n квадрат плюс 5n плюс 2 – это O от n квадратов, потому что если мы возьмем любое n не меньше 1, то 3n квадрат плюс 5n плюс 2 – это максимум 3n квадрат плюс 5n квадрат плюс 2n квадрат, что составляет 10n квадратов. Некоторое кратное n в квадрате. Таким образом, если посмотреть на эти две функции, то они действительно в некотором смысле имеют одинаковую скорость роста. Если вы посмотрите на соотношение между ними, конечно, оно большое, 10n равно 1, но по мере увеличения n оно уменьшается примерно до 3. А когда вы вводите исходные данные, при n равном 100, n квадрат равен миллиону 3n квадрат + 5n + 2 – это немного больше 3 миллионов. Таким образом, это не одна и та же функция. Одна из них явно больше другой, но не намного, не более чем в три раза. На протяжении всего курса мы будем использовать нотацию big-O для представления, в основном, времени работы всех наших алгоритмов. И это дает нам массу преимуществ. Первое, что это дает нам, – это уточнение скорости роста. Как я уже говорил, часто нас интересует, как время работы масштабируется с размером входных данных. И это своего рода артефакт того факта, что нас часто действительно интересует, что происходит, когда мы вводим очень, очень, очень большие входные данные в наш алгоритм. С каким размером мы можем справиться, прежде чем он начнет ломаться? И если вы дадите мне какое-то сложное выражение в терминах входных данных, с большим количеством терминов, то, возможно, будет трудно сравнить два алгоритма. То есть, какой из них больше, будет зависеть от того, какие именно входные данные я использую. Чтобы определить, в чем именно один из них лучше другого, потребуются какие-то утомительные вычисления. Но если посмотреть на вещи асимптотически, что происходит, когда n становится большим? Часто становится гораздо более очевидным, что при очень-очень большом n алгоритм a лучше, чем алгоритм b. Второе, что это дает нам, – это очистка обозначений. Мы можем написать O(n²), вместо 3n² + 5n + 2. И это намного чище и намного проще для работы. Мы можем написать O(n) вместо n + log₂(n) + sin(n). Мы можем написать O(n log(n)) вместо 4n log₂(n) + 7. Обратите внимание, что в большом O нам не нужно указывать основание логарифма, который мы используем. Потому что log₂(n), и log₃(n), и log₁₀(n), и log₇(n), Они отличаются только постоянными кратностями. И вплоть до постоянных кратных, это большое O, которое мы имеем, действительно не волнует. Другим следствием этого является то, что поскольку наша нотация чище, поскольку у нас меньше членов низшего порядка, с которыми приходится иметь дело, это фактически делает алгебру, которую мы должны делать, проще.