В чем большая особенность нотации Big-O в информатике?

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

Я читаю ответы, и я (серьезно) думаю, что big-O недооценивается.

Как кодеры, которые зарабатывают деньги на кодировании, нам нужно знать, что такое big-O и зачем оно нам нужно.

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

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

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

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

Ответ 10

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

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

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

Ответ 11

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

Ответ 12

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

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

Ответ 13

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

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

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