"Böyük O" sadə İngilis izahı nədir?

Mən mümkün qədər az rəsmi təsəvvür və sadə riyaziyyat istərdim.

4660
28 янв. Arec Barrwin 28 yanvar təyin etdi 2009-01-28 14:10 '09 at 14:10 'da 2009-01-28 14:10
@ 39 cavab
  • 1
  • 2

Tez bir qeyd, demək olar ki, Theta (ikitərəfli əlaqəli) təyinatı ilə Böyük O qeydini (üst sərhəd olan) qarışdırır. Təcrübəmdə qeyri-akademik şəraitdə müzakirələr tipikdir. Hər hansı bir qarışıqlıqdan üzr istəmək.


Bu qrafiklə Big O-nin mürəkkəbliyini görsən:

2019

6267
28 янв. Cavab 28 yanvar cletus verilir 2009-01-28 14:18 '09 at 14:18 'da 2009-01-28 14:18

Alqoritmanın necə ölçülməsini göstərir.

O (n 2 ) : Kvadratik mürəkkəblik kimi tanınır

  • 1 element: 1 saniyə
  • 10 məhsul: 100 saniyə
  • 100 məhsul: 10,000 saniyə

Xahiş olunur ki, maddələrin sayı 10 dəfə artır, lakin vaxt 10 dəfə artır. Əsasən, n = 10 və bu səbəbdən O (n 2 ) bizə n2 olan miqyaslı bir faktor verir, bu da 10 2dir .

O (n) : Doğrusal mürəkkəblik kimi tanınır

  • 1 element: 1 saniyə
  • 10 məhsul: 10 saniyə
  • 100 məhsul: 100 saniyə

Bu dəfə ədədlərin sayı həm də vaxtın 10 dəfə artır. n = 10, beləliklə O (n) miqyaslama faktoru 10dur.

O (1) : Sabit mürəkkəblik kimi tanınır

  • 1 element: 1 saniyə
  • 10 xal: 1 saniyə
  • 100 məhsul: 1 saniyə

Elementlərin sayı hələ də 10 dəfə artır, lakin ölçmə faktoru O (1) hər zaman 1dir.

O (log n) : Logaritmik mürəkkəblik kimi tanınır

  • 1 element: 1 saniyə
  • 10 məhsul: 2 saniyə
  • 100 məhsul: 3 saniyə
  • 1000 maddələr: 4 saniyə
  • 10.000 ədəd: 5 saniyə

Hesablamaların sayı yalnız giriş dəyərinə görə artır. Buna görə, bu halda, əgər hər hesablama 1 saniyə çəkilirsə, giriş logası n tələb olunan vaxtdır, beləliklə, log n .

Bunun mahiyyəti budur. Riyazımı kəsdilər, buna görə tam olaraq n 2 və ya hər hansı bir ola bilməz, lakin miqyasda dominant faktor olacaqdır.

682
28 янв. Ray Hidayat tərəfindən cavabı Jan 28 2009-01-28 14:28 '09 da 14:28 'da 2009-01-28 14:28

Big-O notasyonu (həmçinin "asimptotik böyümə" notası da adlandırılır) funksiyaların daimi faktorlar və başlanğıc ətrafında olanları görməməzlikdə göründüyü kimi görünür. Biz bunu şeylərin miqyası necə olduğunu danışmaq üçün istifadə edirik.


əsasları

"kifayət qədər" böyük girişlər üçün ...

  • f(x) ∈ O(upperbound) f " upperbound daha sürətli upperbound " upperbound
  • f(x) ∈ Ɵ(justlikethis) f " justlikethis kimi böyüyür" justlikethis
  • f(x) ∈ Ω(lowerbound) f "aşağı lowerbound daha yavaş artır" lowerbound

Böyük-O notation daimi faktorlara 9x² : 9x² funksiyası " 9x² " kimi tam olaraq böyüyən 10x² . Big-O asimptotik notasiya da 10x² funksiyası 10x² " 10x² - x + 2 " kimi 10x² "asimptotik olmayan şeylər" ("mənbəyə yaxın olanlar" və ya "problemin ölçüsü kiçikdir") ilə 10x² .

Niyə denklemin kiçik hissələrini gözardı etmək istəyirsiniz? Böyük və böyük miqyaslı tərəzi verildikdə, tənliklərin böyük hissələrində olduqca böyük tutulduqları üçün; onların töhfəsi cırtdan və alakasız olur. (Məsələn bölməyə baxın.)

Başqa sözlə desək, sonsuzluğa yaxınlaşdıqca, bütün bunlar nisbətdən asılıdır. O(...) faktiki vaxtı bölsəniz, böyük giriş sərhədində daimi bir faktor olur. Səmimi olaraq, bu mantiqlıdır: funksiyaları bir-birinə "miqyaslı", əgər başqa birini almaq üçün bir-birinə çarpar. Biz dedikdə ...

 actualAlgorithmTime(N) ∈ O(bound(N)) eg "time to mergesort N elements is O(N log(N))" 

... bu, "kifayət qədər böyük" problemlərin miqdarı üçün (əgər mənşəyə yaxın olan əşyalara baxmayaraq) bir neçə sabit (məsələn, tamamilə tərtib olunmuş 2.5) belədir:

 actualAlgorithmTime(N) eg "mergesort_duration(N) " ────────────────────── < constant ───────────────────── < 2.5 bound(N) N log(N) 

Sobalar üçün bir çox variant var; tez-tez "ən yaxşı" seçim alqoritmi "daimi amil" kimi tanınır ... lakin biz ən böyük şərtləri görməməz olduğumuz kimi tez-tez onu görməməzik ("Davamlı amillər" bölməsinə baxın, niyə onlar adətən əhəmiyyətsizdir). Bundan əlavə, yuxarıda göstərilən tənliyi bir məhdudiyyət kimi nəzərdən keçirə bilərsiniz: "Ən pis halda, vaxtın 2,5 dəfə (bizi maraqlandırmadığımız daimi amil N*log(N) faktiki olaraq N*log(N) ) ".

Ümumiyyətlə, O(...) ən faydalıdır, çünki biz tez-tez ən pis vəziyyətdə davranışa diqqət yetiririk. f(x) prosessor və ya yaddaş istifadə kimi "pis" bir şey təmsil edirsə, " f(x) ∈ O(upperbound) " " upperbound - ən pis halda prosessor / yaddaş istifadə ssenarisi" deməkdir.


Proqramlar

Tamamilə riyazi bir quruluş olaraq, böyük-O notation, işləmə vaxtı və yaddaşından danışmaqla məhdudlaşmır. Ölçmənin mənalı olduğu hər şeyin asimptotiklərini müzakirə etmək üçün bunu istifadə edə bilərsiniz, məsələn:

  • ( Ɵ(N²) , xüsusilə də N(N-1)/2N(N-1)/2 Ɵ(N²) arasında mümkün əl )
  • zamanın bir funksiyası kimi bir növ viral marketinq görən olabiləcək olan ehtimal sayda adam
  • veb səhifənin gecikməsinin CPU, GPU və ya kompüter qrupundakı prosessor bloklarının sayı ilə ölçülməsi
  • prosessorun istilik gücü transistorlar, gərginlik və s. sayına görə necə ölür.
  • girişin ölçüsündən asılı olaraq alqoritm nə vaxt lazımdır
  • girişin ölçüsündən asılı olaraq alqoritmi çalıştırmak üçün nə qədər yer lazımdır

bir nümunə

Yuxarıda göstərilən əlamət nümunəsi üçün odadakı hər kəs əllərini sarsıtdı. Bu nümunədə #handshakes ∈ Ɵ(N²) . Niyə?

Bir az yemək: əl-ələ sayıları n-seçmək-2 və ya N*(N-1)/2 -ə bərabərdir (hər bir şəxs N-1 bir-birinin əllərini sarsıdır, ancaq bu əlamətlərin sayı ikiqatdır).

2019

ответ дан ninjagecko 08 июля '11 в 7:46 2011-07-08 07:46

РЕДАКТИРОВАТЬ: Быстрое замечание, это почти наверняка смущает нотация Big O (которая является верхней границей) с обозначением Theta (что является одновременно и верхняя и нижняя границы). По моему опыту, это типично для дискуссий в неакадемических условиях. Извинения за любую путаницу.

В одном предложении: по мере увеличения размера вашей работы, сколько времени потребуется, чтобы завершить ее?

Очевидно, что только использование "размера" в качестве входного сигнала и "время, принятое" в качестве вывода — эта же идея применяется, если вы хотите поговорить об использовании памяти и т.д.

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

  • Использование стиральной линии снаружи: при условии, что у вас бесконечно большой задний двор, мытье высыхает в течение O (1). Как бы то ни было, у него будет такое же солнце и свежий воздух, поэтому размер не влияет на время высыхания.

  • Использование сушилки для сушки: вы накладываете 10 рубашек на каждую нагрузку, а затем через час. (Игнорируйте фактические цифры здесь, они не имеют значения.) Таким образом, сушка 50 рубашек занимает примерно в 5 раз дольше, чем высушивание 10 рубашек.

  • Вкладывая все в шкафчик для воздуха: если мы поместим все в одну большую кучу и просто дадим общей теплоте, это займет много времени, пока средние рубашки не высохнут. Я не хотел бы догадываться о деталях, но я подозреваю, что это, по крайней мере, O (N ^ 2) — по мере увеличения нагрузки на стирку, время сушки увеличивается быстрее.

Одним из важных аспектов нотации "большой O" является то, что он не говорит, какой алгоритм будет быстрее для заданного размера. Возьмите хэш-таблицу (строковый ключ, целочисленное значение) и массив пар (строка, целое число). Быстрее найти ключ в хэш-таблице или элемент в массиве на основе строки? (т.е. для массива "найдите первый элемент, в котором строковая часть соответствует заданному ключу".) Хэш-таблицы обычно амортизируются (~ = "в среднем" ) O (1) — после того, как они настроены, для поиска записи в таблице с 100 входами потребуется примерно одно и то же время, как в таблице ввода в 1000 000. Поиск элемента в массиве (на основе контента, а не индекса) является линейным, то есть O (N) — в среднем вам придется посмотреть на половину записей.

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

237
ответ дан Jon Skeet 28 янв. '09 в 14:16 2009-01-28 14:16

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

Nümunələr:

  • O (n): если я удваиваю размер ввода, время выполнения удваивается

  • O (n 2 ): Если размер ввода удваивает количество циклов выполнения

  • O (log n): Если размер ввода удваивается, время выполнения увеличивается на один

  • O (2 n ): если размер ввода увеличивается на единицу, время выполнения удваивается

Размер ввода обычно представляет собой пробел в битах, необходимых для представления ввода.

120
ответ дан starblue 28 янв. '09 в 14:23 2009-01-28 14:23

Обозначение Big O чаще всего используется программистами как приблизительная мера того, как долго будет выполняться вычисление (алгоритм) для полного выражения в зависимости от размера входного набора.

Big O полезен для сравнения того, насколько хорошо будут увеличиваться два алгоритма по мере увеличения количества входов.

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

Во многих случаях "O" алгоритма попадает в один из следующих случаев:

  • O (1) . Время завершения одинаково независимо от размера входного набора. Примером является доступ к элементу массива по индексу.
  • O (Log N) . Время завершения увеличивается примерно в соответствии с log2 (n). Например, 1024 элемента занимают примерно вдвое длиннее 32 элементов, так как Log2 (1024) = 10 и Log2 (32) = 5. Примером является поиск элемента в двоичное дерево поиска (BST).
  • O (N) - время завершения, которое масштабируется линейно с размером входного набора. Другими словами, если вы удвоите количество элементов во входном наборе, алгоритм займет примерно вдвое больше. Примером является подсчет количества элементов в связанном списке.
  • O (N Log N) - время завершения увеличивается на количество элементов, умноженное на результат Log2 (N). Примером этого является куча сортировки и быстрая сортировка .
  • O (N ^ 2) . Время завершения примерно равно квадрату числа элементов. Примером этого является сортировка пузырьков .
  • O (N!) . Время завершения - это факторный набор входных данных. Примером этого является решение проблемы коммивояжера.

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

98
ответ дан cdiggins 05 сент. '11 в 19:31 2011-09-05 19:31

Big O - это просто способ "выразить" себя обычным способом: "Сколько времени и пространства требуется для запуска моего кода?".

Вы можете часто видеть O (n), O (n 2 ), O (nlogn) и т.д., все это просто способы показать; Как изменяется алгоритм?

O (n) означает, что Big O является n, и теперь вы можете подумать: "Что такое n!?" Ну "n" - количество элементов. Imaging вы хотите искать элемент в массиве. Вам нужно будет посмотреть на каждый элемент и как "Вы правильный элемент/элемент?" в худшем случае элемент находится по последнему индексу, а это значит, что потребовалось столько же времени, сколько есть элементов в списке, поэтому, чтобы быть общим, мы говорим: "О, эй, я - справедливое заданное количество ценностей!".

Итак, вы можете понять, что означает "n 2 ", но, чтобы быть более конкретным, играйте с мыслью, что у вас есть простой, самый простой алгоритм сортировки; BubbleSort. Этот алгоритм должен просматривать весь список для каждого элемента.

Мой список

  • 1
  • 6
  • 3

Здесь поток:

  • Сравните 1 и 6, что является самым большим? Ок 6 находится в правильном положении, двигаясь вперед!
  • Сравните 6 и 3, о, 3 меньше! Давайте переместим это, Ok, список изменился, нам нужно начать с самого начала!

Это O n 2 потому что вам нужно посмотреть на все элементы в списке, где есть "n". Для каждого элемента вы снова смотрите на все предметы, для сравнения это также "n", поэтому для каждого элемента вы смотрите "n" раз, что означает n * n = n 2

Надеюсь, это так просто, как вы этого хотите.

Но помните, что Big O - это просто способ, чтобы вы себя вписывали в манеру времени и пространства.

77
ответ дан Filip Ekberg 28 янв. '09 в 14:14 2009-01-28 14:14

Big O описывает фундаментальный масштабный алгоритм.

Существует много информации о том, что Big O не говорит вам о данном алгоритме. Он сокращается до кости и дает только информацию о масштабирующем характере алгоритма, в частности, как использование ресурсов (время мысли или память) алгоритма масштабируется в ответ на "размер ввода".

Рассмотрим разницу между паровым двигателем и ракетой. Они не просто разные разновидности одного и того же (как, скажем, двигатель Prius и двигатель Lamborghini), но они представляют собой совершенно разные виды силовых установок. Паровой двигатель может быть быстрее, чем игрушечная ракета, но паровой поршневой двигатель не сможет достичь скорости орбитальной ракеты-носителя. Это связано с тем, что эти системы имеют разные масштабирующие характеристики в отношении соотношения требуемого топлива ( "использование ресурсов" ) для достижения заданной скорости ( "размер входного сигнала" ).

Почему это так важно? Потому что программное обеспечение занимается проблемами, которые могут отличаться по размеру до трех триллионов. Подумайте об этом на мгновение. Соотношение между скоростью, необходимой для перемещения на Луну и скоростью ходьбы человека, составляет менее 10 000: 1, и это абсолютно крошечный по сравнению с диапазоном программного обеспечения с размерами входных данных. И поскольку программное обеспечение может столкнуться с астрономическим диапазоном в размерах входных данных, существует потенциал для сложности алгоритма Big O, его фундаментальный масштабный характер, чтобы превзойти любые детали реализации.

Рассмотрим пример канонической сортировки. Bubble-sort - это O (n 2 ), а merge-sort - O (n log n). Скажем, у вас есть два приложения для сортировки, приложение A, которое использует сортировку пузырьков и приложение B, которое использует сортировку слиянием, и пусть говорят, что для размеров ввода около 30 элементов приложение A на 1000 раз быстрее, чем приложение B при сортировке. Если вам никогда не придется сортировать более 30 элементов, то очевидно, что вам следует отдать предпочтение приложению A, поскольку оно намного быстрее при этих размерах ввода. Однако, если вы обнаружите, что вам, возможно, придется сортировать десять миллионов элементов, то то, что вы ожидаете, - это то, что приложение B фактически заканчивается в тысячи раз быстрее, чем приложение A в этом случае, полностью из-за того, как каждый алгоритм масштабируется.

52
ответ дан Wedge 28 янв. '09 в 16:12 2009-01-28 16:12

Вот простой английский бестиарий, который я обычно использую при объяснении общих разновидностей Big-O

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

O (1):

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

O (log n):

Эта сложность такая же, как O (1) , за исключением того, что она немного хуже. Для всех практических целей вы можете рассматривать это как очень большое постоянное масштабирование. Разница в работе между обработкой 1 тыс. И 1 млрд. Единиц составляет всего лишь шесть.

О (п):

Стоимость решения проблемы пропорциональна размеру проблемы. Если ваша проблема удваивается по размеру, стоимость решения удваивается. Поскольку большинство проблем необходимо каким-то образом отсканировать в компьютер, как ввод данных, чтение дисков или сетевой трафик, это, как правило, доступный коэффициент масштабирования.

O (n log n):

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

О (п 2 ):

Растет как квадрат, где n - длина стороны квадрата. Это тот же самый темп роста, что и "сетевой эффект", где каждый в сети может знать всех остальных в сети. Рост дорог. Большинство масштабируемых решений не могут использовать алгоритмы с таким уровнем сложности, не выполняя значительную гимнастику. Это обычно относится ко всем другим многочленам сложности - O (n k ) - также.

О (2 п ):

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

36
ответ дан Andrew Prock 28 янв. '14 в 2:09 2014-01-28 02:09

Big O - это показатель того, сколько времени/пространства использует алгоритм относительно размера его ввода.

Если алгоритм O (n), то время/пространство будет увеличиваться с той же скоростью, что и его вход.

Если алгоритм O (n 2 ), то время/пространство увеличивается со скоростью его квадрата ввода.

və s

34
ответ дан Brownie 28 янв. '09 в 14:19 2009-01-28 14:19

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

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

Поскольку они являются приближениями, мы используем в выражении букву "O" (Big Oh) в качестве условного обозначения, чтобы сообщить читателю, что мы делаем грубое упрощение. (И чтобы убедиться, что никто не ошибочно думает, что выражение в любом случае точнее).

Если вы читаете "О" как значение "по порядку" или "приблизительно", вы не ошибетесь. (Я думаю, что выбор Big-Oh мог быть попыткой юмора).

Единственное, что эти выражения "Big-Oh" пытаются сделать, это описать, насколько программное обеспечение замедляется, поскольку мы увеличиваем объем данных, которые программное обеспечение должно обрабатывать. Если мы удваиваем объем данных, которые необходимо обработать, требуется ли в два раза больше программного обеспечения, чтобы завершить работу? Десять раз? На практике существует очень ограниченное количество выражений большого О-О, с которыми вы столкнетесь и о чем беспокоиться:

Хорошее:

  • O(1) Константа . Программа выполняет одно и то же время для запуска независимо от того, насколько велик вход.
  • O(log n) Логарифмическая : время выполнения программы увеличивается только медленно, даже при большом увеличении размера ввода.

Плохо:

  • O(n) Линейный : время выполнения программы увеличивается пропорционально размеру ввода.
  • O(n^k) Полиномиальный : - время обработки растет быстрее и быстрее - как функция полинома - по мере увеличения размера ввода.

... и уродливый:

  • O(k^n) Экспоненциальный Время выполнения программы очень быстро увеличивается даже при умеренном увеличении размера проблемы - практично обрабатывать небольшие наборы данных с помощью экспоненциальных алгоритмов.
  • O(n!) Факториал Продолжительность программы будет больше, чем вы можете позволить себе ждать чего угодно, кроме самых маленьких и самых тривиальных, кажущихся наборов данных.
30
ответ дан William Payne 29 мая '13 в 16:51 2013-05-29 16:51

Что такое простое английское объяснение Big O? С как можно меньшим формальным определением и простой математикой.

Простое английское объяснение необходимости нотации Big-O:

Когда мы программируем, мы пытаемся решить проблему. То, что мы кодируем, называется алгоритмом. Обозначение Big O позволяет стандартизовать худшую производительность наших алгоритмов. Спецификации оборудования меняются со временем, а усовершенствования аппаратного обеспечения могут сократить время, затрачиваемое на выполнение алгоритмов. Но замена аппаратного обеспечения не означает, что наш алгоритм будет лучше или улучшен с течением времени, так как наш алгоритм все тот же. Поэтому, чтобы позволить нам сравнивать разные алгоритмы, чтобы определить, лучше ли это или нет, мы используем нотацию Big O.

Обычный английский Объяснение того, что такое Big O Notation:

Не все алгоритмы работают за один и тот же промежуток времени и могут варьироваться в зависимости от количества элементов на входе, которые мы будем называть n. Исходя из этого, мы рассматриваем анализ худшего случая или верхнюю границу времени выполнения, когда n становится больше и больше. Мы должны знать, что такое n, потому что многие из нот Big O ссылаются на него.

30
ответ дан James Oravec 22 февр. '13 в 4:00 2013-02-22 04:00

Хорошо, мои 2центы.

Big-O, скорость увеличения ресурса, потребляемого программой, wrt Проблема-экземпляр размера

Ресурс: может быть общее время процессора, может быть максимальным объемом оперативной памяти. По умолчанию используется процессорное время.

Скажем, что проблема заключается в "Найти сумму",

 int Sum(int*arr,int size){ int sum=0; while(size-->0) sum+=arr[size]; return sum; } 

problem-instance = {5,10,15} == > problem-instance-size = 3, iterations-in-loop = 3

problem-instance = {5,10,15,20,25} == > problem-instance-size = 5 iterations-in-loop = 5

Для ввода размера "n" программа растет со скоростью "n" итераций в массиве. Следовательно, Big-O есть N, выраженное как O (n)

Скажем, что проблема заключается в "Найти комбинацию",

  void Combination(int*arr,int size) { int outer=size,inner=size; while(outer -->0) { inner=size; while(inner -->0) cout<<arr[outer]<<"-"<<arr[inner]<<endl; } } 

problem-instance = {5,10,15} == > problem-instance-size = 3, total-iterations = 3 * 3 = 9

problem-instance = {5,10,15,20,25} == > problem-instance-size = 5, total-iterations = 5 * 5 = 25

Для ввода размера "n" программа растет со скоростью "n * n" итераций в массиве. Следовательно, Big-O является N 2 выраженным как O (n 2 )

27
ответ дан Ajeet Ganga 23 авг. '11 в 7:06 2011-08-23 07:06

Простым простым ответом может быть:

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

27
ответ дан AlienOnEarth 13 нояб. '13 в 13:23 2013-11-13 13:23

Обозначение Big O - это способ описания верхней границы алгоритма в терминах пространства или времени выполнения. N - количество элементов в задаче (размер массива, количество узлов в дереве и т.д.). Нам интересно описать время выполнения, когда n становится большим.

Когда мы говорим, что какой-то алгоритм O (f (n)), мы говорим, что время выполнения (или требуемое пространство) этим алгоритмом всегда ниже, чем некоторые постоянные времена f (n).

Сказать, что бинарный поиск имеет время работы O (logn), означает, что существует некоторая константа c, которую вы можете умножить на log (n), которая всегда будет больше, чем время работы бинарного поиска. В этом случае вы всегда будете иметь постоянный коэффициент сопоставления log (n).

Другими словами, где g (n) - время работы вашего алгоритма, мы говорим, что g (n) = O (f (n)), когда g (n) <= c * f (n), когда n > k, где c и k - некоторые константы.

24
ответ дан John C Earls 17 июля '10 в 5:29 2010-07-17 05:29

"Что такое простое английское объяснение Big O? С небольшим формальным как возможная и простая математика".

Такой красивый и короткий вопрос кажется, по крайней мере, заслуживающим столь же короткого ответа, как ученик может получить во время обучения.

Обозначение Big O просто говорит, сколько времени * алгоритм может работать внутри, в терминах только количества входных данных **.

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

Хорошо, что так замечательно в нотации Big O, если это то, что он делает?

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

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

22
ответ дан Joseph Myers 15 авг. '13 в 4:57 2013-08-15 04:57

Пример алгоритма (Java):

20
ответ дан Khaled.K 23 марта '13 в 18:19 2013-03-23 18:19

Big O

f (x) = O (g (x)), когда x переходит в (например, a = + ∞), означает, что существует такая функция k, что:

  • f (x) = k (x) g (x)

  • k ограничена в некоторой окрестности точки a (если a = + ∞, это означает, что найдутся числа N и M такие, что для любого x > N, | k (x) | < M).

Другими словами, на простом английском языке: f (x) = O (g (x)), x → a, означает, что в окрестности af разбивается на произведение g и некоторую ограниченную функцию.

Малый o

Кстати, здесь для сравнения определение малых o.

f (x) = o (g (x)), когда x переходит в a, означает, что существует такая функция k, что:

  • f (x) = k (x) g (x)

  • k (x) переходит в 0, когда x переходит в a.

Nümunələr

  • sin x = O (x), когда x → 0.

  • sin x = O (1), когда x → + ∞,

  • x 2 + x = O (x), когда x → 0,

  • x 2 + x = O (x 2 ) при x → + ∞,

  • ln (x) = o (x) = O (x), когда x → + ∞.

Diqqət! Обозначение с равным знаком "=" использует "поддельное равенство": верно, что o (g (x)) = O (g (x)), но false что O (g (x)) = o (g (x)). Точно так же нормально писать "ln (x) = o (x) при x → + ∞", но формула "o (x) = ln (x)" не имеет смысла.

Другие примеры

  • O (1) = O (n) = O (n 2 ) при n → + ∞ (но не наоборот, равенство является "поддельным" ),

  • O (n) + O (n 2 ) = O (n 2 ) при n → + ∞

  • O (O (n 2 )) = O (n 2 ), когда n → + ∞

  • O (n 2 ) O (n 3 ) = O (n 5 ) при n → + ∞


Вот статья Википедии: https://en.wikipedia.org/wiki/Big_O_notation

18
ответ дан Alexey 16 марта '13 в 0:18 2013-03-16 00:18

Обозначение Big O - это способ описания того, как быстро алгоритм будет работать с учетом произвольного количества входных параметров, которые мы будем называть "n". Это полезно в информатике, потому что разные машины работают на разных скоростях и просто говорят, что алгоритм занимает 5 секунд, не говорит вам многого, потому что, хотя вы можете запускать систему с окто-ядерным процессором 4,5 ГГц, я могу работать 15-летняя, 800 МГц система, которая может занять больше времени, независимо от алгоритма. Поэтому вместо указания того, насколько быстро алгоритм работает с точки зрения времени, мы говорим, как быстро он работает в терминах количества входных параметров или "n". Таким образом, описывая алгоритмы, мы можем сравнивать скорости алгоритмов, не принимая во внимание скорость самого компьютера.

17
ответ дан Brian 25 июня '14 в 23:32 2014-06-25 23:32

Не уверен, что я буду вносить свой вклад в эту тему, но все же думал, что буду делиться: однажды я нашел этот пост в блоге , чтобы иметь довольно полезные (хотя и очень простые) объяснения и примеры на Big O:

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

11
ответ дан Priidu Neemre 29 сент. '12 в 23:54 2012-09-29 23:54

Вы хотите знать все, что нужно знать о большом O? Я тоже.

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

Теперь давайте поговорим о работе. Большую часть времени мне не нравится работа. Вам нравится работать? Возможно, это так, но я уверен, что нет.

Мне не нравится идти на работу. Я не люблю тратить время на работу. Если бы у меня был свой путь, я бы хотел просто поиграть и повеселиться. Вы чувствуете то же, что и я?

Теперь время от времени мне приходится идти на работу. Это печально, но верно. Итак, когда я нахожусь на работе, у меня есть правило: я стараюсь делать меньше работы. Как можно ближе к работе. Затем я играю!

Итак, вот большая новость: большой O может помочь мне не делать работу! Я могу играть больше времени, если знаю большой О. Меньше работы, больше играю! Это то, что помогает мне большое О.

Теперь у меня есть работа. У меня есть этот список: один, два, три, четыре, пять, шесть. Я должен добавить все в этот список.

Ничего себе, я ненавижу работу. Но, хорошо, я должен это сделать. Итак, я иду.

Один плюс два - три... плюс три - шесть... и четыре... Я не знаю. Я потерял. Мне слишком тяжело это делать в моей голове. Я не очень забочусь о такой работе.

Так что давайте не будем делать работу. Пусть мы с тобой подумаем, как это тяжело. Сколько работы я должен сделать, чтобы добавить шесть номеров?

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

Здесь идет большой O, чтобы рассказать нам, насколько тяжело эта математика.

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

Ну, я не буду делать работу, чтобы добавить их сейчас. Но я знаю, как это было бы тяжело. Это будет шесть добавлений.

О нет, теперь у меня больше работы. Sheesh. Кто делает такие вещи?!

Теперь они просят меня добавить от одного до десяти! Зачем мне это делать? Я не хотел добавлять от одного до шести. Чтобы добавить от одного до десяти... ну... это будет еще сложнее!

Насколько тяжелее это было бы? Сколько еще работы я должен был сделать? Нужно ли больше или меньше шагов?

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

Я не хочу добавлять прямо сейчас. Я просто хочу подумать о том, как сложно это добавить. И, надеюсь, играть, как только смогу.

Чтобы добавить от одного до шести, это некоторая работа. Но видите ли вы, чтобы добавить от одного до десяти, это больше работает?

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

Теперь мы должны сделать новую работу. О нет. Мне вообще не нравится эта работа.

Новая работа: добавить все вещи от одного до n.

Подождите! Что такое n? Я пропустил это? Как я могу добавить от одного до n, если вы не скажете мне, что такое n?

Ну, я не знаю, что такое n. Мне не сказали. Вы были? Нет? Ну что ж. Поэтому мы не можем выполнять эту работу. Уф.

Но, хотя мы не будем делать эту работу сейчас, мы можем догадаться, насколько это было бы тяжело, если бы мы знали n. Мы должны были бы добавить n вещей, правильно? Конечно!

Теперь вот большой О, и он расскажет нам, как тяжело эта работа. Он говорит: добавить все вещи от одного к N, один за другим, это O (n). Чтобы добавить все эти вещи, я знаю, что должен добавить n раз.] [1] Это большой O! Он рассказывает нам, как трудно выполнять какую-то работу.

Для меня, я думаю о большом О, как о большом, медленном, босс-мужчине. Он думает о работе, но он этого не делает. Он мог бы сказать: "Эта работа идет быстро". Или он мог бы сказать: "Эта работа настолько медленная и трудная!" Но он не выполняет эту работу. Он просто смотрит на работу, а затем рассказывает нам, сколько времени это займет.

Мне очень нравятся большие О. Почему? Я не люблю работать! Никто не любит работать. Вот почему мы все любим большой O! Он рассказывает нам, как быстро мы можем работать. Он помогает нам думать о том, как тяжелая работа.

Ух, больше работы. Теперь давайте не будем делать работу. Но давайте сделаем план сделать это шаг за шагом.

Они дали нам колоду из десяти карт. Все они перепутаны: семь, четыре, два, шесть... не прямые. И теперь... наша задача - сортировать их.

Ergh. Это звучит как большая работа!

Как мы можем сортировать эту колоду? У меня есть план.

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

Когда колода закончена, я спрашиваю: я сделал обмен карточками в этом проходе? Если это так, я должен сделать это еще раз, сверху.

В какой-то момент, в какое-то время, не будет никаких свопов, и наша колода будет сделана. Так много работы!

Хорошо, сколько будет работы, чтобы сортировать карты с этими правилами?

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

Big O, помогите мне!

Входит Big O и говорит: для колоды n карт, сортировать их таким образом будет сделано в O (N квадрат) времени.

Почему он говорит в квадрате?

Ну, вы знаете, что n квадратов n раз n. Теперь, я понимаю: n проверенных карт, вплоть до того, что может быть n раз через колоду. Это две петли, каждая из которых имеет n шагов. Это означает, что нужно много работы. Очень много работы, конечно!

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

Теперь вот где большой O - наш друг.

Big O указывает на это: по мере того, как n становится большим, когда мы сортируем карты, работа становится МНОГО БОЛЬШЕ ЖЕСТКО, чем старая операция "просто добавьте эти вещи". Как мы это знаем?

Хорошо, если n становится действительно большим, нам все равно, что мы можем добавить к n или n квадрату.

При больших n квадрат n больше n.

Big O говорит нам, что сортировать вещи сложнее, чем добавлять вещи. O (n квадрат) больше, чем O (n) при больших n. Это означает: если n становится действительно большим, для сортировки смешанной колоды n вещей ДОЛЖНО занимать больше времени, чем просто добавлять n смешанных вещей.

Big O не решает эту работу для нас. Big O рассказывает нам, как тяжело работать.

У меня колода карт. Я их сортировал. Вы помогли. Təşəkkür edirik.

Есть ли более быстрый способ сортировки карт? Может ли большой О помочь нам?

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

В этом новом способе сортировки колоды мы не проверяем пары карт так, как мы это делали некоторое время назад. Вот ваши новые правила для сортировки этой колоды:

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

Два: я играю колоду на той карте, которую вы выбрали. Что это за игра? как я могу играть? Ну, я иду от стартовой карты вниз, один за другим, и я искал карту, которая выше, чем игровая карта.

Три: я иду с торцевой карты вверх, и я ищу карту, которая ниже, чем у игровой карты.

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

В какой-то момент этот цикл (от двух до трех) закончится. Это заканчивается, когда обе половины этого поиска встречаются на игровой карте. Затем мы просто разделили колоду с картой, которую вы выбрали на первом шаге. Теперь все карты рядом с стартом более низкие, чем карта игры; и карты ближе к концу более высокие, чем игра-карта. Прохладный трюк!

Четыре (и это забавная часть): теперь у меня две маленькие колоды, еще одна низкая, чем у игровой карты, и еще одна высокая. Теперь я иду на первый шаг, на каждую маленькую колоду! То есть, я начинаю с первого шага на первой маленькой колоде, и когда эта работа завершена, я начинаю с шага Один на следующей небольшой колоде.

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

Что это называется? Он называется Quick Sort! Этот вид был сделан человеком под названием CAR Hoare , и он назвал его Quick Sort. Теперь Quick Sort используется все время!

Quick Sort разбивает большие колоды в маленьких. То есть он разбивает большие задачи в маленьких.

Хммм. Думаю, там может быть правило. Чтобы сделать большие задачи небольшими, раскройте их.

Это довольно быстро. Как быстро? Big O говорит нам: в этом случае нужна O (n log n) работа, в среднем случае.

Является ли это более или менее быстрым, чем первый вид? Big O, пожалуйста, помогите!

Первый вид был O (n квадрат). Но Quick Sort - O (n log n). Вы знаете, что n log n меньше n квадратов, для больших n, правильно? Ну, вот как мы знаем, что Quick Sort быстро!

Если вам нужно сортировать колоду, что лучше? Ну, вы можете делать то, что хотите, но я бы выбрал Quick Sort.

Почему я выбираю Quick Sort? Конечно, я не люблю работать! Я хочу, чтобы работа была выполнена, как только я смогу это сделать.

Как узнать, что Quick Sort меньше работает? Я знаю, что O (n log n) меньше, чем O (n квадрат). O меньше, поэтому Quick Sort работает меньше!

Теперь ты знаешь моего друга, Биг О. Он помогает нам делать меньше работы. И если вы знаете большой O, вы можете делать меньше работы тоже!

Ты узнал все это со мной! Ты такой умный! Большое вам спасибо!

Теперь, когда работа выполнена, отпустите игру!


[1]: Есть способ обмануть и добавить все вещи от одного до n, все в одно время. Некоторый парень по имени Гаусс узнал об этом, когда ему было восемь. Я не настолько умный, поэтому не спрашивайте меня, как он это сделал .

11
ответ дан johnwbyrd 27 дек. '15 в 13:34 2015-12-27 13:34

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

 statement; 

Постоянно. Время выполнения инструкции не изменится относительно N

 for ( i = 0; i < N; i++ ) statement; 

Является линейным. Время работы петли прямо пропорционально N. Когда N удваивается, время работы также выполняется.

 for ( i = 0; i < N; i++ ) { for ( j = 0; j < N; j++ ) statement; } 

Квадратично. Время работы двух петель пропорционально квадрату N. Когда N удваивается, время работы увеличивается на N * N.

 while ( low <= high ) { mid = ( low + high ) / 2; if ( target < list[mid] ) high = mid - 1; else if ( target > list[mid] ) low = mid + 1; else break; } 

Логарифмически. Время работы алгоритма пропорционально количеству раз, когда N можно разделить на 2. Это связано с тем, что алгоритм разделяет рабочую область пополам с каждой итерацией.

 void quicksort ( int list[], int left, int right ) { int pivot = partition ( list, left, right ); quicksort ( list, left, pivot - 1 ); quicksort ( list, pivot + 1, right ); } 

Является N * log (N). Время выполнения состоит из N циклов (итеративных или рекурсивных), которые являются логарифмическими, поэтому алгоритм представляет собой комбинацию линейных и логарифмических.

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

Qeyd Ничто из этого не учитывало лучшие, средние и худшие меры. У каждого будет своя нотация Big O. Также обратите внимание, что это ОЧЕНЬ упрощенное объяснение. Big O является наиболее распространенным, но он также более сложным, чем я показал. Существуют и другие обозначения, такие как большая омега, маленькая о и большая тета. Вероятно, вы не столкнетесь с ними вне курса анализа алгоритмов.

9
ответ дан nitin kumar 30 янв. '15 в 10:00 2015-01-30 10:00

Скажите, что вы заказываете Гарри Поттера: заполните 8-кинематографическую коллекцию [Blu-ray] из Amazon и одновременно загрузите одну и ту же коллекцию фильмов в Интернете. Вы хотите проверить, какой метод выполняется быстрее. Доставка занимает почти один день, и загрузка завершена примерно на 30 минут раньше. Большой! Так что это плотная гонка.

Что делать, если я закажу несколько Blu-ray фильмов, таких как The Lord of the Rings, Twilight, The Dark Knight Trilogy и т.д. и загружаю все фильмы онлайн одновременно? На этот раз доставка по-прежнему занимает целый день, но онлайн-загрузка занимает 3 дня. Для покупок в Интернете количество приобретенных товаров (входных данных) не влияет на время доставки. Выход постоянный. Мы называем это O (1) .

Для онлайн-загрузки время загрузки прямо пропорционально размерам файлов видео (вход). Мы называем это O (n) .

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

Qeyd Обозначение Big O представляет собой наихудший сценарий алгоритма. Предположим, что O (1) и O (n) являются наихудшими сценариями примера выше.

Ссылка : http://carlcheo.com/compsci

9
ответ дан raaz 06 дек. '15 в 9:01 2015-12-06 09:01

Предположим, что мы говорим об алгоритме A , который должен что-то делать с набором данных размера n .

Тогда O( <some expression X involving n> ) означает простой английский:

Если вам не повезло при выполнении A, это может привести к операциям X (n) полная.

Как бы то ни было, существуют определенные функции (считайте их реализацией X (n) ), которые имеют тенденцию возникать довольно часто. Они хорошо известны и легко сравниваются (примеры: 1 , Log N , N , N^2 , N! и т.д.)

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

В общем, нашей целью будет найти или структурировать алгоритм A таким образом, чтобы он имел функцию X(n) , которая возвращает как можно меньшее число.

9
ответ дан Kjartan 25 окт. '13 в 18:11 2013-10-25 18:11

Если у вас есть подходящее понятие бесконечности в голове, то есть очень краткое описание:

Обозначение Big O говорит вам о стоимости решения бесконечно большой проблемы.

И более того

Постоянные факторы незначительны

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

Тем не менее, может быть обнаружено что-либо "большее", чем постоянный фактор.

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


Если вышеизложенное не имеет смысла, то у вас нет совместимого интуитивного понятия бесконечности в вашей голове, и вы, вероятно, должны игнорировать все вышеперечисленное; единственный способ, которым я знаю, чтобы эти идеи были строгими или объяснить их, если они еще не являются интуитивно полезными, - это научить вас большой нотации O или что-то подобное. (хотя, как только вы хорошо поймете большую нотацию O в будущем, может быть целесообразно пересмотреть эти идеи)

8
ответ дан Hurkyl 16 мая '15 в 19:02 2015-05-16 19:02

Что такое простое английское объяснение "Big O"?

Очень быстрое примечание:

O в "Big O" означает "Order" (или точно "порядок")
так что вы могли бы получить его идею буквально, что он использовал, чтобы заказать что-то, чтобы сравнить их.

  • "Big O" делает две вещи:

    1. Оценивает количество шагов, которые ваш компьютер применяет для выполнения задачи.
    2. Содействовать процессу сравнить с другими, чтобы определить, хорошо это или нет?
    3. "Big O" достигает вышеупомянутых двух со стандартными Notations .
  • Есть семь наиболее используемых обозначений

    1. O (1), означает, что ваш компьютер выполняет задание с 1 шагом, отлично, заказано №1
    2. O (logN), означает, что ваш компьютер выполняет задачу с шагами logN , это хорошо, logN № 2
    3. O (N), завершите задачу с N шагов, ее справедливость, заказ № 3
    4. O (NlogN), завершает задачу с O(NlogN) шагов O(NlogN) , это не хорошо, Order No.4
    5. O (N ^ 2), выполнить задание с N^2 шагами, это плохо, Приказ №5
    6. O (2 ^ N), выполните задачу с шагами 2^N , это ужасно, Приказ №6
    7. O (N!), Выполните задачу с N! шаги, это ужасно, Приказ № 7

2019

ответ дан JawSaw 13 апр. '18 в 15:36 2018-04-13 15:36

Простейший способ взглянуть на него (на простом английском языке)

Мы пытаемся увидеть, как количество входных параметров влияет на время работы алгоритма. Если время работы вашего приложения пропорционально количеству входных параметров, то говорят, что оно находится в Big O of n.

Вышеприведенное утверждение является хорошим началом, но не полностью истинным.

Более точное объяснение (математическое)

Предположим, что

n = количество входных параметров

T (n) = Фактическая функция, которая выражает время работы алгоритма как функцию n

c = константа

f (n) = приближенная функция, выражающая время работы алгоритма как функцию n

Тогда, что касается Big O, аппроксимация f (n) считается достаточно хорошей, пока выполняется условие ниже.

 lim T(n) ≤ c×f(n) n→∞ 

Уравнение читается как Поскольку n стремится к бесконечности, T n, меньше или равно c раз f из n.

В большой записи O это написано как

 T(n)∈O(n) 

Это читается как T из n в большом O из n.

Назад на английский

Основываясь на приведенном выше математическом определении, если вы говорите, что ваш алгоритм является большим O из n, это означает, что он является функцией n (количество входных параметров) или быстрее . Если ваш алгоритм Big O of n, то он также автоматически является большим O из n квадрата.

Big O of n означает, что мой алгоритм работает как минимум так быстро. Вы не можете взглянуть на ноту Big O на свой алгоритм и сказать, что он медленный. Вы можете сказать только быстро.

Отметьте этот для видеоурока на Big O от UC Berkley. На самом деле это простая концепция. Если вы услышите, что профессор Шелчук (он же учитель уровня Бога) объясняет это, вы скажете: "О, это все!".

6
ответ дан developer747 16 авг. '15 в 23:38 2015-08-16 23:38

Это очень упрощенное объяснение, но я надеюсь, что оно охватывает самые важные детали.

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

В зависимости от N и X для вашего алгоритма потребуются некоторые операции, например, в случае WORST это операции 3(N^2) + log(X) .

Так как Big-O не слишком заботится о постоянном множителе (aka 3), Big-O вашего алгоритма O(N^2 + log(X)) . В основном это означает "количество операций, которые ваш алгоритм требует для наихудших шкал с этим".

4
ответ дан nkt 11 окт. '15 в 21:00 2015-10-11 21:00

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

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

Я бы посоветовал вам увидеть это видео с YouTube, которое подробно объясняет Big O Notation с примерами кода.

2019

ответ дан Shivprasad Koirala 11 мая '18 в 11:33 2018-05-11 11:33

Если я хочу объяснить это 6-летнему ребенку, я начну рисовать некоторые функции, например, f (x) = x и f (x) = x ^ 2, и спросить ребенка, какая функция будет верхней функцией в верхней части страница. Затем мы приступим к рисованию и увидим, что x ^ 2 выигрывает. "Кто победит" - это функция, которая растет быстрее, когда x стремится к бесконечности. Таким образом, "функция x в Big O из x ^ 2" означает, что x растет медленнее, чем x ^ 2, когда x стремится к бесконечности. То же самое можно сделать, когда x стремится к 0. Если мы нарисуем эти две функции для x от 0 до 1, то x будет верхней функцией, поэтому "функция x ^ 2 находится в Big O для x для x, стремящегося к 0". Когда ребенок станет старше, я добавляю, что действительно Большой О может быть функцией, которая растет не быстрее, а так же, как данная функция. Более того, константа отбрасывается. Таким образом, 2x в Big O из x.

3
ответ дан user3745123 13 июня '15 в 18:29 2015-06-13 18:29
  • 1
  • 2

Другие вопросы по меткам или Задайте вопрос