Каково грандиозное предприятие о Нотации "большого О" в информатике?

Big-O рассказывает о сложности алгоритма с точки зрения размера его входов. Это существенно , если Вы хотите знать, как алгоритмы будут масштабироваться. Если Вы проектируете большой сайт и у Вас много пользователей, то время, необходимое Вам для обработки этих запросов, очень важно. Если у вас много данных и вы хотите хранить их в структуре, вы должны знать, как это эффективно сделать, если вы собираетесь написать что-то, что не займет миллион лет.

Не то, чтобы Big-O нотация сама по себе поможет вам. А в том, что если вы понимаете нотацию Big-O, вы понимаете наихудшую сложность алгоритмов. По сути, Big-O дает вам высокоуровневое представление о том, какие алгоритмы быстрые, какие медленные, а какие компромиссы. Я не понимаю, как вы можете понять последствия чего-либо, скажем, в библиотеке .NET collection, если вы этого не понимаете.

Я не буду вдаваться в подробности здесь, так как этот вопрос задавался много раз , но достаточно сказать, что это то, что вы должны понять . Вот довольно высоко проголосовавший предыдущий вопрос Big-O , чтобы вы могли начать.

Нет, мне тоже было интересно, но теперь я думаю о big-O почти каждый раз, когда пользуюсь библиотекой.

Big-O позволяет вам узнать асимптотическое время работы любой функции, таким образом вы можете решить, является ли структура данных A быстрее структуры данных B для ваших целей.

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

Нет, это действительно помогает понять эффективность различных алгоритмов.

Если вы уделите время пониманию Big O, то каждый раз, когда вы будете сидеть и кодировать цикл, вы будете думать: "Как я могу сделать это более эффективным?". - что хорошо :)

Да, это просто "академическое упражнение". Будьте уверены, до тех пор, пока некоторые тупые академики делают такие упражнения, вы сможете изо дня в день делать хорошую работу по программированию :-)

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

Для дополнительной информации посмотрите хорошую академическую книгу или отличные ответы выше ...

Это вопрос, который (почти) все задают во время изучения CS, особенно если они планируют быть промышленными разработчиками.

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

С другой стороны, я обнаружил, что некоторые школы слишком сильно подталкивают своих студентов к математической/алгебраической стороне вопроса, а не к его важности для использования в реальном мире. Студенты, которые менее заинтересованы в этой алгебраической стороне, испытывают отвращение. IMHO, нет необходимости для большинства студентов CS, чтобы знать, как вычислить Большой О за пределами основ. Заставляя такие вещи, как теорема Мастеров, не заставит их ценить это.

Помните, что big-O говорит Вам, как алгоритмы масштабируются с большим количеством входов, это не говорит Вам, что алгоритм ведьмы быстрее справляется с Вашей задачей.

Построение пирамид - это O(n), а сортировка их изображений - в лучшем случае O(n log n), это не значит, что построить их быстрее, чем сделать слайд-шоу

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

Big-O важен при разработке алгоритмов больше, чем ежедневные взломы. Обычно вам не нужно знать Big-O, если только вы не работаете с большим количеством данных (т.е. если вам нужно отсортировать массив, состоящий из 10 000 элементов, а не 10). Во многих случаях это библиотеки, которые обрабатывают хитрости для вас (например, встроенная функция sort), но в некоторых случаях вам нужно сделать это самому.

Суть в том, что Big-O довольно легко выучить, так что просто выучите его . Это поможет вам в ряде случаев.

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

Я читаю ответы, и я (серьезно) думаю, что "Большой О" недооценивается.

Как программистам, которые зарабатывают деньги на кодировании, мы должны знать, что такое "большой О" и зачем он нам нужен.

Позвольте мне объяснить, что я думаю: "Большая нотация" - это эффективность/производительность вашей работы. Вы должны знать, как быстро работает ваш код, когда входы становятся больше, потому что в реальной жизни вы не можете знать точное количество входов. Более того, вы не можете сравнить два разных алгоритмических подхода без асимптотической нотации, поэтому, если вы хотите выбрать лучший, вы сравните их с big-O и посмотрите, какой из них подходит для вашей ситуации. Оба могут быть неэффективными, но вы будете знать, какой из них лучше.

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

Нотация Big-O - это формализация этих компромиссов, позволяющая разработчикам программного обеспечения говорить о них на одном языке. Возможно, вам никогда не придется официально доказывать характеристики Big-O разрабатываемого вами алгоритма, но если вы не понимаете концепцию на абстрактном уровне, то, скорее всего, вы не пойдете на компромисс в разрабатываемом программном обеспечении. .

Big-O - это средство измерения или значимой остановки работы алгоритма с точки зрения времени. Так что если в этом отношении необходимо провести какую-либо оптимизацию, big-o - ценный инструмент. Это основная глава по классам алгоритмов и структур данных. Я согласен с другими ответами, в которых упоминается, что вы можете не использовать его непосредственно в своей повседневной работе по программированию, но даже этот повседневный код имеет производительность, которую можно измерить при необходимости.

Подумай об эффективности, мой друг!

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

В большой нотации O(n) - пробегая через вашу огромную кучу несортированных бумаг, и O(1) - просматривая указатель по имени.