Свет в конце туннеля. Мне просто нужно было дважды проверить, правильно ли я сказал, что прошло 12 недель с тех пор, как я начал эту программу Flatiron Software Engineer. Я чувствую себя уверенно в своем фундаменте и в своих способностях создать элементарное полнофункциональное веб-приложение. Откровенно говоря, я был впечатлен количеством знаний и идей, которые были брошены в меня, и даже больше тем количеством, которое я действительно сохранил, и тем, что я могу создать с этими идеями. Когда я рассматривал возможность участия в одной из этих программ по программированию, мне сказали, что она не заменит полную степень в области компьютерных наук, и это абсолютно правильно. Нас учат, что необходимо знать основы, чтобы взяться за дело в качестве младшего веб-разработчика, которому нужно еще многому научиться.
Проходя эту программу Flatiron, насколько я понимаю, мы рассмотрели множество более теоретических аспектов общения с компьютерами, тем более что мы имеем дело с такими языками высокого уровня, как Javascript и Ruby. Нам нужно изучить основы, такие как работа с массивами, функциональное программирование, объектно-ориентированное программирование, создание алгоритмов для сортировки, сложения или поиска целого числа или объекта. Много хороших вещей, но больше о том, как, а не о том, почему. В попытке окунуться в более возвышенные мысли, которые назидаются в высоких степенях CS, и подготовиться к тому, что, как меня заверили, будет включено в строгий процесс собеседования, чтобы стать младшим веб-разработчиком, я читал. по нотации Big O и временной сложности.
Прежде чем я перейду к этому, я хотел бы предварить это аналогичным предупреждением для других моих блогов. Это я говорю вслух, чтобы лучше понять тему, о которой я хотел бы узнать больше, и если есть какие-либо вопиющие ошибки, пожалуйста, проявите понимание и / или протяните руку и дайте мне знать, где я ошибся. Но я думаю, что если что-то явно не так, я надеюсь, что старая интернет-пословица о том, что лучший способ найти ответ на вопрос — это не задавать прямо, а утверждать неправильный ответ и ждать, пока Интернет скажет вам, насколько вы неправы.
Ладно, три абзаца мнений и вздор, давайте приступим к делу. Временная сложность и нотация Big O являются выражением увеличения времени по мере увеличения входных данных для вашей функции. Таким образом, в компьютерном программировании временная сложность в основном зависит от того, насколько быстр ваш алгоритм. Да, довольно легко предположить, что сложная функция с большим количеством шагов будет обрабатываться компьютером дольше, чем простая функция. Но сколько еще? Что ж, мы собираемся посмотреть на некоторые функции и поговорить об этом.
В этом блоге мы коснемся трех основных временных сложностей: постоянной, линейной и квадратичной. Первое, постоянное время является самым основным. Это просто постоянное время при изменении ввода. Время, необходимое для запуска функции, всегда будет одинаковым, независимо от размера входных данных. В нотации Big O это записывается как O (1). Примером постоянного времени является доступ к значению в массиве.
константа обр = [ 24, 6, 89, 12]
Приб [2] = 89
Или другим примером может быть очень простой условный оператор, в котором нет дополнительных функций обратного вызова. На графике постоянная временная сложность будет выглядеть так.
Второй тип — линейная временная сложность. На языке Big O это записывается как O(n). Линейная сложность — это в основном классический рост y=mx+b. По мере роста входных данных время выполнения будет расти в прямой зависимости. Примером этого является цикл for по массиву для получения суммы всех значений.
На графике линейная сложность будет выглядеть так:
Третий и последний тип, которого мы коснемся сегодня, — это квадратичное время. В нотации O это O (n²). Это означает, что он экспоненциальный. По мере увеличения входных данных время, необходимое для завершения вычислений, будет увеличиваться. Примером этого могут быть методы пузырьковой сортировки, выбора или сортировки вставками. Действительно хороший способ определить, является ли что-то квадратичной временной сложностью, - это наличие цикла for внутри другого цикла for. На графике это будет выглядеть так:
Насколько я понимаю то, что я читал об этом, и мой класс исчисления в колледже, большая нотация O, по сути, является производной. Я уверен, что это не так и что это намного сложнее, но для того, насколько я вижу, что это полезно, это имеет смысл. Это просто мера во времени. Все компьютеры разные, разное оборудование, разное программное обеспечение, работающее в фоновом режиме и занимающее память. Измерение изменения времени по мере изменения входных данных — хороший способ сгладить игровое поле и определить, насколько быстр и эффективен ваш алгоритм. Теперь я вижу, что если вы понимаете временную сложность данной функции, вы можете определить, каков наиболее эффективный способ решения проблемы.
Дальнейшее чтение:
