Насколько эффективна и масштабируема ваша программа?
Большой О, это действительно важная тема. Без этой темы вряд ли можно увидеть интервью.
И это концепция, которая прослужит долго в мире разработчиков. Независимо от того, являетесь ли вы старшим разработчиком, который занимается кодированием в течение длительного времени, или новичком, только начинающим, это незаменимая концепция, о которой нужно знать.
Это не только помогает на собеседовании, но и играет жизненно важную роль в написании программ.
Итак, позвольте мне начать с рассказа небольшого опыта, который привел меня к практическому изучению структур данных и алгоритмов.
Несколько дней назад я участвовал в моем первом Google Code Jam: онлайн-соревновании по программированию, где вам будет предложен набор задач для поиска решения. И я только что прошел квалификацию в первый раунд. Было 3 проблемы, которые нужно было решить в течение 2.30 часов. Я был уверен, что не смогу решить все, но, по крайней мере, хотел решить одну. Итак, я попытался решить одну из них, но большинство моих попыток приводили к ошибке Превышен лимит времени (также были некоторые неправильные ответы ...).
И это из-за того, что мое решение не было правильным алгоритмическим способом.
Что вызвало эту ошибку TLE?
Хорошо. Ответ прост. Это произошло из-за несовершенного большого О. Я использовал так много вложенных циклов, что заставляло программу работать экспоненциально по мере того, как набор данных становился все больше и больше. И именно здесь я осознал важность структур данных и алгоритмов. Если бы я придерживался правильного подхода, я мог бы сэкономить большую часть времени, и моя программа была бы идеальной. Поэтому я начал с изучения Big O, первого шага в освоении структур данных и алгоритмов.
Кстати, в конце концов, я даже не доделал ни одного из них в первом раунде. LOL :)
Довольно моих вещей. давай начнем. Но прежде чем мы начнем, я хочу задать вам вопрос.
Как вы определите хороший код?
Допустим, есть два друга, Тим и Том, и у них обоих есть решение проблемы. В этом случае как мы можем узнать, чей код лучше? Ответ таков: есть 2 вещи, которые делают код хорошим, лучшим и лучшим. Они есть
- Читаемость
- Масштабируемость
В этой статье мы обсудим масштабируемость, поскольку Big O попадает в эту категорию. Так как же измерить масштабируемость? Чтобы лучше это понять, допустим, у нас есть функция, которая находит Землю среди множества планет.
Для указанной выше функции давайте измерим ее масштабируемость с точки зрения временной сложности, зная, сколько времени потребовалось для выполнения.
Обратите внимание, что масштабируемость измеряется как с точки зрения сложности времени, так и сложности пространства. Но пока давайте остановимся только на временной сложности.
Мы можем сделать это в javascript, добавив performace.now() как в начале, так и в конце функции. Наконец, мы вычитаем t1-t0, чтобы получить общее время, затраченное на выполнение функции. И так как это небольшая функция, время, которое потребуется, составит 0 миллисекунд (приблизительно).
Но что, если в массиве более 10 000 элементов. Время увеличилось бы, но не так значительно, правда? Компьютеры сегодня очень быстрые. Но каждый раз, когда вы запускаете программу, может быть небольшая разница во времени.
И это полностью зависит от того, насколько быстро работает процессор вашего компьютера, какие программы уже используются и т. Д.
Итак, если бы мы применили эту методологию к коду Тима и Тома, можем ли мы сказать, что код Тима (4 миллисекунды) лучше, чем код Тома (6 миллисекунд), поскольку для его выполнения потребовалось на 2 миллисекунды меньше? Нет, это неправильный способ судить. Как было сказано ранее, время может варьироваться в зависимости от других внешних факторов, например, какой процессор вы используете, какие другие программы работают одновременно? так далее..
Хорошо. тогда как мы это измерим?
Ответ - большой минус.
Так что же такое Big O?
Большой O - это способ оценить эффективность вашей программы. Как было сказано ранее, каждый может написать решение проблемы, если будет достаточно времени, как Тим и Том, верно? Дело в том, насколько хорошо наша программа работает во время выполнения. Усложняется ли увеличение ввода? И это то, что будет искать большинство ведущих технологических гигантов, таких как Google, Amazon и т. Д.
Итак, Big O - это язык, который мы используем для определения времени выполнения функции / алгоритма.
Мы можем использовать Big O, чтобы сравнить два разных алгоритма, таких как код Тима и Тома, и сказать, какой из них лучше, независимо от производительности их компьютеров. И у алгоритма могут быть следующие разные "большие" ".
Это может показаться сложным, но по мере нашего продвижения становится легче понять.
Из диаграммы выше вы можете видеть, что количество операций значительно увеличивается при увеличении элементов в некоторых случаях [O (n!), O (2 ^ n), O (n²)]. И количество операций в некоторых случаях остается почти таким же [O (log n), O (1) и т. Д.].
Вот как мы определяем хороший код с точки зрения временной сложности с помощью Big O. Мы определенно не хотим, чтобы наш алгоритм / функция оставались в красной области, поскольку вы видите, что это ужасно.
Всякий раз, когда мы определяем масштабируемость с точки зрения временной сложности с помощью Big O, мы просто имеем в виду,
Когда ввод становится все больше и больше, насколько замедляется наш алгоритм. Чем меньше он замедляется, тем лучше он похож на зелено-желтые области.
Итак, с этого момента вместо использования performance.now() для вычисления времени мы будем использовать Big O для измерения количества шагов, необходимых алгоритму по мере увеличения входных данных.
И мы узнаем, как вычислить Big O ?, что такое O (n), O (1) и т. Д.? в следующей статье, так как это уже довольно много. Я не хочу писать слишком много в одной статье. Так что вернемся к следующей статье :)
Кстати, все эти знания исходили от Андрея. Мой очень хороший инструктор и многие другие студенты. Все хлопки здесь посвящены ему :)
