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

Question

Я бы предпочел как можно меньше формального определения и простую математику.

Answer 1

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

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

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

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

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

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

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

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

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

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

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

А вот и большой O, чтобы сказать нам, насколько сложна эта математика.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Большой О, помоги мне!

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

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

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

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

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

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

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

Для больших n квадрат n больше, чем n.

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

Big O не решает работу за нас. Большой О говорит нам, насколько тяжелая работа.

У меня есть колода карт. Я их отсортировал. Вы помогли Спасибо.

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

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

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

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

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

Три:Я иду от конечной карты вверх и ищу карту ниже, чем сплайс-карта.

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

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

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

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

Как называется этот сорт? Это называется Быстрая сортировка! Этот сорт был сделан человеком по имени C. А. Р. Хоар и он назвал это быстрой сортировкой. Теперь быстрая сортировка привыкает все время!

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

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

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

Это более или менее быстро, чем первый сорт? Большой О, пожалуйста, помогите!

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

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

Почему я выбираю быструю сортировку? Я не люблю работать, конечно! Я хочу, чтобы работа была выполнена как можно скорее.

Откуда мне знать, что быстрая сортировка - это меньше работы? Я знаю, что O (n log n) меньше, чем O (n в квадрате). O более маленькие, поэтому быстрая сортировка - меньше работы!

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

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

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

---

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

Answer 2

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

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

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

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

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

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

Answer 3

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

Что если я закажу несколько Blu-ray фильмов, таких как «Властелин колец», «Сумерки», «Трилогия Темного рыцаря» и т. Д., И загружу все фильмы онлайн одновременно? На этот раз доставка все еще занимает один день, но онлайн-загрузка занимает 3 дня. Для покупок в Интернете количество купленных товаров (входных данных) не влияет на время доставки. Выход постоянный. Мы называем это O (1) .

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

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

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

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

Answer 4

У меня есть более простой способ понять сложность времени Наиболее распространенной метрикой для вычисления сложности времени является нотация 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)).

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

• Подробнее на: Здесь

Answer 5

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

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

А кроме того

Постоянные факторы пренебрежимо малы

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

Хотя можно обнаружить что-либо «большее», чем постоянный коэффициент.

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

---

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

Answer 6

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

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

О в «Большом О» называется «Порядком» (или, точнее, «Порядком»)
чтобы вы могли буквально понять, что он используется для заказа чего-то для сравнения.

• «Большой О» делает две вещи:

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

• Существует семь наиболее часто используемых обозначений

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

Предположим, вы получили обозначение O(N^2), не только вы уверены, что метод выполняет N * N шагов для выполнения задачи, но также вы видите, что он не так хорош, как O(NlogN) из своего рейтинга.

Пожалуйста, обратите внимание на порядок в конце строки, просто для вашего лучшего понимания. Существует более 7 обозначений, если рассматриваются все возможности.

В CS набор шагов для выполнения задачи называется алгоритмами.
В терминологии обозначение Big O используется для описания производительности или сложности алгоритма.

Кроме того, Big O устанавливает наихудший случай или измеряет верхние границы.
Вы можете обратиться к Big-Ω (Big-Omega) для лучшего случая.

нотация Big-Ω (Big-Omega) (статья) | Ханская академия

• Резюме
  «Большой O» описывает производительность алгоритма и оценивает его.

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

Answer 7

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

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

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

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

Пусть

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

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

с = константа

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

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

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

Уравнение читается как Когда n приближается к бесконечности, T of n меньше или равно c раз f от n.

В больших обозначениях O это записывается как

T(n)∈O(n)

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

Вернуться на английский

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

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

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

Answer 8

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

https://rob -bell.net / 2009/06 / а-новички-гид-к-большой-о-записи /

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

Любой, кто читал Программирование Жемчуг или любую другую информатику книги и не имеет оснований по математике ударит в стену когда они достигли глав, в которых упоминается O (N log N) или другие, казалось бы, сумасшедший синтаксис. Надеюсь, эта статья поможет вам получить понимание основ большого О и логарифмов.

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

O (1)

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

bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null; } O(N)

O (N)

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

bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 

O (N * 1 025 * 2 )

O (N ² ) представляет алгоритм, производительность которого напрямую пропорционально квадрату размера входного набора данных. Это общий с алгоритмами, которые включают вложенные итерации по данным задавать. Более глубокие вложенные итерации приведут к O (N ³ ), O (N ⁴ ) и т. Д.

bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}

* * О тысяча тридцать семь (2

^{N * 1 039 *) * 1 040 * O (2 N ) обозначает алгоритм, рост которого удваивается с каждым дополнением к набор входных данных. Кривая роста функции O (2 N ) экспоненциальный - начиная с очень мелкого, затем поднимаясь метеорически. Примером функции O (2 N ) является рекурсивное вычисление Фибоначчи Номера: int Fibonacci(int number) { if (number <= 1) return number; return Fibonacci(number - 2) + Fibonacci(number - 1); } Логарифмы * * тысяча пятьдесят-одна Логарифмы немного сложнее объяснить, поэтому я буду использовать общий Пример: Бинарный поиск - это метод, используемый для поиска в отсортированных наборах данных. Оно работает выбрав средний элемент набора данных, по существу медиана, и сравнивает его с целевым значением. Если значения соответствуют ему вернет успех. Если целевое значение выше, чем значение элемент зонда это займет верхнюю половину набора данных и выполнить ту же операцию против него. Аналогично, если целевое значение ниже, чем значение элемента зонда, он будет выполнять операция против нижней половины. Это будет продолжать вдвое данных установить для каждой итерации, пока значение не будет найдено или пока оно не может больше не разбивать набор данных. Этот тип алгоритма описывается как O (log N). Итеративное деление пополам наборов данных, описанных в примере двоичного поиска, приводит к росту кривая, которая достигает пика в начале и медленно выравнивается как размер наборов данных увеличивается, например, набор входных данных, содержащий 10 элементов занимает одну секунду, набор данных, содержащий 100 элементов занимает две секунды, и набор данных, содержащий 1000 элементов, займет три секунд. Удвоение размера набора входных данных мало влияет на его рост как после одной итерации алгоритма набора данныхбудет вдвое меньше и, следовательно, наравне с входными данными, установленными на половину размер. Это делает алгоритмы, такие как бинарный поиск, чрезвычайно эффективными при работе с большими наборами данных.}

Answer 9

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

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

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

Так, например, предположим, что алгоритм занимает 5 записей, а время, необходимое для его обработки, составляет 27 секунд. Теперь, если мы увеличим количество записей до 10, алгоритм займет 105 секунд.

Проще говоря, время, взятое в квадрате от количества записей. Мы можем обозначить это как O (n ^ 2) . Это символическое представление называется обозначением Big O.

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

Например, посмотрите на приведенную ниже функцию «Function1», которая принимает коллекцию и выполняет обработку первой записи. Теперь для этой функции производительность будет одинаковой, независимо от того, поставили вы 1000, 10000 или 100000 записей. Таким образом, мы можем обозначить его как O (1) .

void Function1(List<string> data)
{
string str = data[0];
}

Теперь см. Нижеприведенную функцию «Функция2 ()». В этом случае время обработки будет увеличиваться с увеличением количества записей. Мы можем обозначить производительность этого алгоритма, используя O (n) .

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

Когда мы видим обозначение Big O для любого алгоритма, мы можем классифицировать его по трем категориям производительности: -

1. Журнал и постоянная категория: - Любой разработчик хотел бы видеть производительность своего алгоритма в этой категории.
2. Линейный: - Разработчик не захочет видеть алгоритмы в этой категории, пока не останется его последний вариант или единственный параметр.
3. Экспоненциальный: - Здесь мы не хотим видеть наши алгоритмы, и необходима доработка.

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

Я бы рекомендовал вам посмотреть это 10-минутное видео, в котором обсуждается Big O с примером кода

https://www.youtube.com/watch?v=k6kxtzICG_g

Answer 10

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

Допустим, ваш алгоритм решения проблемы зависит от некоторых «факторов», например, давайте сделаем это N и X.

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

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