Ответ 1

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

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

Ответ 2

Обозначение Big-O означает грубо "заданную операцию по количеству работы, N, сколько времени вычисления, пропорционального N, принимает алгоритм?". Например, сортировка массива размера N может принимать N ^ 2, Nlog (N) и т.д.

У этого нет никакого количества входных данных, чтобы действовать. Так что это не O(anything).

Еще хуже; это не технически алгоритм. Алгоритм - это метод вычисления значения математической функции - математические функции - это отображение от одного входа к выходу. Так как это не принимает никакого ввода и ничего не возвращает, это не функция, в математическом смысле. Из Википедии:

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

Что это, технически, является системой управления. Из Википедии;

Система управления - это устройство или набор устройств, которые управляют, команды, направляет или регулирует поведение других устройств или системы.

Для людей, желающих получить более подробный ответ о различии между математическими функциями и алгоритмами, а также более мощные способности компьютеров делать побочные эффекты, такие как вывод консоли, отображение графики или управление роботами, имеют читайте эту статью о гипотезе Сильной Церкви-Тьюринга

Абстрактный

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

Принятие взаимодействия в качестве новой парадигмы затруднено темой Сильной Церкви-Тьюринга (SCT), распространенным убеждением, что машины Тьюринга (TM) захватывают все вычисления, поэтому модели вычислений, более выразительные, чем ТМ, невозможны. В этой статье мы показываем, что SCT переосмысливает оригинальную тезису Церкви-Тьюринга (CTT) таким образом, каким никогда не предназначался Тьюринг; его общепринятая эквивалентность оригиналу - это миф. Мы определяем и анализируем исторические причины широко распространенной веры в ПКТЗ. Только принимая, что это ложь, мы можем начать взаимодействие как альтернативную парадигму вычисления

Ответ 3

Нет, ваш код имеет временную сложность O(2^|<DeltaTime>|),

Для правильного кодирования текущего времени.
Пожалуйста, позвольте мне сначала извиниться за мой английский.

Что такое и как работает Big O в CS

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

В случае анализа алгоритма эти две величины: not вход (для которого сначала нужно иметь функцию "measure" ) и время выполнения.
Это длина кодирования экземпляра задачи ¹ и представляющая интерес метрика.

Обычно используемые метрики

• Количество шагов, необходимых для завершения алгоритма в данной модели вычисления.
• Пространство требуется, если такое понятие существует, по модели вычисления.

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

Также часто подразумевается, что мы можем использовать полиномиально связанную кодировку вместо исходной, например, функция, которая ищет массив от начала до конца, имеет сложность O(n), несмотря на то, что кодирование экземпляра такой массив должен иметь длину n*b+(n-1), где b - (постоянное) количество символов каждого элемента. Это связано с тем, что b считается константой модели вычисления, и поэтому выражение выше и n асимптотически одно и то же.

Это также объясняет, почему алгоритм, подобный Trial Division, является экспоненциальным алгоритмом, несмотря на по существу являющийся for(i=2; i<=sqr(N); i++) подобным алгоритмом ³.

См. this.

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

Итак, это не о "вводе" или о том, что "нет ввода".

Пример исследования

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

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

В частности, экземпляр:

<DeltaTime>

Где <> означает любое, не патологическое, кодирование выбора.

См. ниже очень важные пояснения.

Таким образом, ваше большое время сложности O просто O(2^|<DeltaTime>|), потому что вы выполняете ряд итераций, которые зависят от значения текущего времени. Нет смысла ставить другие числовые константы, поскольку асимптотическая нотация полезна, поскольку она устраняет константы (так, например, использование O(10^|<DeltaTime>|*any_time_unit) бессмысленно).

Если сложная часть

Мы сделали одно важное предположение выше: модель вычисления оценивает время ⁵ а по времени я имею в виду (реальное?) физическое время. В стандартной вычислительной модели нет такой концепции, ТМ не знает времени, мы связываем время с количеством шагов, потому что так работает наша реальность ⁴.

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

Чтобы понять это, следует отметить, что ничто не мешает Framework использовать поддельное время, которое выполняется в два, пять, десять раз быстрее, чем физическое время. Таким образом, ваш код будет работать в "половине", "одной пятой", "одной десятой" "времени".

Это отражение важно для выбора кодирования <DeltaTime>, это по существу сжатый способ записи < (CurrentTime, TimeInFuture) > . Поскольку время не существует в priory, кодирование CurrentTime вполне может быть словом Now (или любым другим выбором) за день до этого может быть закодировано как вчера, там, нарушив предположение, что длина кодирования увеличивается, когда физическое время идет вперед (и уменьшается один из DeltaTime)

Мы должны правильно моделировать время в нашей вычислительной модели, чтобы сделать что-то полезное.

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

Ваша неразбериха, если таковая имеется, возникает из-за того, что слово "время" в фразах "Какова его временная сложность"? и "Сколько времени это займет?" означает очень разные вещи

Увы, в терминологии используются одни и те же слова, но вы можете попробовать использовать "сложность шагов" в своей голове и задать себе свой вопрос, я надеюсь, что это поможет вам понять, что ответ действительно есть ^ _ ^

¹ Это также объясняет необходимость асимптотического подхода, поскольку каждый экземпляр имеет другую, но не произвольную длину.
² Надеюсь, я использую правильный английский термин здесь. ³ И поэтому мы часто находим log(log(n)) термины в математике.
⁴ Id est, шаг должен занимать некоторый конечный, но не нулевой и не связанный промежуток времени.
⁵ Это означает, что вычислительный режим как знание физического времени в нем, то есть может выражать его с его терминами. Аналогия заключается в том, как дженерики работают в среде .NET.

Ответ 4

Хотя здесь есть множество замечательных ответов, позвольте мне немного перефразировать их все.

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

• Мы можем рассматривать ваш алгоритм как постоянную функцию, которая принимает любой ввод любого размера, игнорирует его, ждет фиксированное количество времени и заканчивается. В этом случае его время выполнения равно f (n) = const, и это алгоритм O (1) -time. Это то, что вы ожидали услышать, не так ли? Да, это технически, O (1) -алгоритм.
• Мы можем рассматривать TwentyYearsLater как представляющий интерес параметр типа "входной размер". В этом случае время выполнения равно f (n) = (n-x), где x - это "сейчас время" в момент вызова. Если рассматривать этот путь, это алгоритм O (n) -time. Ожидайте этот контр-аргумент всякий раз, когда вы показываете свой технически O (1) -алгоритм другим людям.
• О, но подождите, если k = TwentyYearsLater - это вход, тогда его размер n - это, фактически, количество бит, необходимых для его представления, то есть n = log (k). Следовательно, зависимость между размером ввода n и временем выполнения f (n) = 2 ^ n - x. Похоже, ваш алгоритм просто стал экспоненциально медленным! Тьфу.
• Другим входным сигналом программы является поток ответов, заданных ОС, в последовательность вызовов DateTime.Now в цикле. Мы можем себе представить, что вся эта последовательность предоставляется в качестве входных данных в момент запуска программы. Среда выполнения может считаться зависящей от свойства этой последовательности, а именно ее длины до первого элемента TwentyYearsLater. В этом случае время выполнения снова f (n) = n, а алгоритм O (n).

Но опять же, в вашем вопросе вы даже не сказали, что вас интересует время исполнения. Что, если вы имели в виду использование памяти? В зависимости от того, как вы моделируете ситуацию, вы можете сказать, что алгоритм - это O (1) -момент или, возможно, O (n) -момент (если для реализации DateTime.Now требуется отслеживать всю последовательность вызова после этого).

И если ваша цель состояла в том, чтобы придумать что-то нелепое, почему бы вам не войти и сказать, что вас интересует, как размер кода алгоритма в пикселях на экране зависит от выбранного уровня масштабирования. Это может быть что-то вроде f (zoom) = 1/zoom, и вы можете с гордостью объявить свой алгоритм размером O (1/n) -pixel!

Ответ 5

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

Итак, если вы возьмете этот код и запустите его на машине с системным временем 1 января 1970 года, для завершения потребуется 65 лет, независимо от того, насколько быстро компьютер (может быть какое-то изменение, если его часы неисправны). Если вы берете этот код и выполняете его на машине с системным временем 2 января 2035 года, она будет завершена почти мгновенно.

Я бы сказал, что ваш вход n, January 1st, 2035 - DateTime.Now, и это O (n).

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

Что касается этого:

Я подумываю использовать фрагмент кода [отредактированный код] как занятый цикл, чтобы помещать его в шутку, когда кто-то запрашивает алгоритм определенной сложности. Правильно ли это?

Нет, не совсем. Другие ответы охватывали это, поэтому я просто хотел упомянуть об этом. Вы не можете в целом сопоставлять годы исполнения с любой большой записью O. Например. Невозможно сказать 20 лет исполнения = O (n ^ 87) или что-то еще в этом отношении. Даже в алгоритме, который вы дали, я мог бы изменить TwentyYearsFromNow на год 20110, 75699436 или 123456789, а big-O все еще O (n).

Ответ 6

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

Здесь вы действительно имеете дело только с одним объектом фиксированного размера. Таким образом, применение большого анализа O сильно зависит (в первую очередь?) От того, как вы определяете свои условия.

Например, вы могли бы означать вывод на печать в целом и наложение ожидания так долго, что любой разумный объем данных будет/будет напечатан точно в тот же период времени. Вы также должны добавить немного больше, чтобы несколько необычные (если не совсем ошибочные) определения получить очень далеко, - особенно, анализ большого вывода обычно определяется с точки зрения количества фундаментальных операций, необходимых для выполнения (но обратите внимание, что сложность также может рассматриваться с точки зрения использования памяти, а не только использования/операций использования ЦП).

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

Ответ 7

big-O относительно чего?

Кажется, вы интуитивно поняли, что twentyYearsLater - это "enter". Если вы действительно написали свою функцию как

void helloWorld(int years) {
   // ...
}

Это было бы O (N), где N = годы (или просто сказать O(years)).

Я бы сказал, что ваш алгоритм O (N) по сравнению с любым числом, которое вы должны записать в строке кода, начиная с twentyYearsLater =. Но люди обычно не рассматривают числа в фактическом исходном коде как входные данные. Они могут рассматривать ввод командной строки в качестве входного сигнала или ввод сигнатуры функции как входной сигнал, но, скорее всего, не сам исходный код. Это то, о чем вы спорите со своим другом - это "вход"? Вы настроили свой код таким образом, чтобы он интуитивно выглядел как вход, и вы можете определенно спросить его большое время работы O в отношении числа N в строке 6 вашей программы, но если вы используете такой выбор по умолчанию в качестве входных данных вам действительно нужно быть явным.

Но если вы принимаете ввод как нечто более обычное, например, в командной строке или в входе в функцию, то вообще нет выхода, а функция - O (1). Это занимает двадцать лет, но поскольку big-O не изменяется до постоянного кратного, O (1) = O (двадцать лет).

Аналогичный вопрос: каково время выполнения:

void sortArrayOfSizeTenMillion(int[] array)

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

Ответ 8

Этот "алгоритм" правильно описан как O (1) или постоянное время. Утверждалось, что нет никакой информации для этой программы, поэтому нет N для анализа с точки зрения Big Oh. Я не согласен с тем, что нет ввода. Когда это скомпилировано в исполняемый файл и вызывается, пользователь может указать любой ввод произвольной длины. Эта длина ввода равна N.

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

Ответ 9

Одна вещь, о которой я удивляюсь, еще не упоминалась: примечание "большой О" - это верхняя граница!

Проблема, которую все заметили, заключается в том, что нет N, описывающего входные данные для алгоритма, поэтому с Big-O-анализом нечего делать. Тем не менее, это легко смягчается некоторыми базовыми обманами, такими как принятие int n и печать "Hello World" n раз. Это обойдет эту жалобу и вернется к реальному вопросу о том, как работает это чудовище DateTime.

Нет реальной гарантии, что цикл while будет завершен. Нам нравится думать, что это нужно в какой-то момент, но учтите, что DateTime.now возвращает системную дату и время. На самом деле нет никакой гарантии, что это монотонно возрастает. Возможно, есть какая-то патологически обученная обезьяна, постоянно меняющая системную дату и время до 21 октября 2015 года 12:00:00 UTC до тех пор, пока кто-то не даст обезьяне обувь с автоматической установкой и навес. Этот цикл может работать бесконечно!

Когда вы на самом деле выкапываете математическое определение обозначений Big-O, они являются верхними границами. Они демонстрируют худший сценарий, как бы маловероятно. Сценарий наихудшего случая * представляет собой бесконечное время выполнения, поэтому мы вынуждены объявить, что для описания сложности выполнения этого алгоритма не существует обозначения большого О, Этого не существует, так как 1/0 не существует.

* Редактирование: из моего обсуждения с KT, не всегда допустимо предполагать, что сценарий, который мы моделируем, с обозначением big-O является наихудшим. В большинстве случаев, если человек не может указать, какой случай мы используем, они намеревались изучить наихудший случай. Тем не менее, вы можете выполнить анализ сложности большого вывода в режиме наилучшего исполнения.

Ответ 10

Каждый правильно указал, что вы не определяете N, но ответ не под наиболее разумной интерпретацией. Если N - длина строки, печатаются и "привет, мир!". является просто примером, поскольку мы можем сделать вывод из описания этого как алгоритма "для hello, world!", тогда алгоритм O (N), потому что у вас может быть строка вывода, которая занимает тридцать, сорок или пятьдесят лет для печати, и вы добавляете к нему только постоянное время. O (kN + c) ∈ O (N).

Добавление:

К моему удивлению, кто-то оспаривает это. Вспомните определения больших O и больших Θ. Предположим, что у нас есть алгоритм, ожидающий постоянного времени c, а затем выводит сообщение длины N в линейном времени. (Это обобщение исходного образца кода.) Позволяет произвольно сказать, что мы ожидаем двадцать лет, чтобы начать печать, и что печать триллиона символов занимает еще двадцать лет. Пусть, например, c = 20 и k = 10¹², но любые положительные действительные числа будут делать. Такова скорость d = c/k (в данном случае 2 × 10⁻¹¹) лет на символ, поэтому наше время выполнения f (N) асимптотически dN + c лет. Всякий раз, когда N > k, dN = c/k N > c. Следовательно, dN < dN + c = f (N) 2 dN для всех N > k и f (N) ∈ Θ (N). Q.E.D.

Ответ 11

Большинство людей, похоже, упускают две очень важные вещи.

• У программы есть вход. Это жестко закодированная дата/время против которого сравнивается системное время. Входы находятся под контролем человека, выполняющего алгоритм, а системного времени нет. Единственное, что может контролировать человек, управляющий этой программой, - это дата/время, которое они жестко закодировали в сравнении.

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

Поэтому он является неопределенным, и наилучшим обозначением "big-O" для этой программы, вероятно, будет O (null) или, возможно, O (NaN).

Ответ 12

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

Такие проблемы, как решетка эратостенена, O (n ^ exp) и, следовательно, разрешимы при малых значениях n. Они вычислимы, просто не в полиномиальном времени (NP), и поэтому, когда его спрашивают, является ли заданное число простым или нет, ответ зависит от величины такого числа. Более того, сложность не зависит от аппаратного обеспечения, поэтому при более быстрых компьютерах ничего не меняется...

Hello World - это не алгоритм, и поэтому бессмысленно пытаться определить его сложность, а это нет. Простым алгоритмом может быть что-то вроде: учитывая случайное число, определить, является ли оно четным или нечетным. Теперь имеет значение, что данный номер имеет 500 цифр? Нет, потому что вам просто нужно проверить, является ли последняя цифра четной или нечетной. Более сложным алгоритмом было бы определить, будет ли заданное число равномерно разделяться на 3. Хотя некоторые числа "легко" вычисляются, другие "жесткие", и это из-за его величины: сравните время, необходимое для определения перегруппировки между число с одной цифрой и другое с 500 цифрами.

Более сложным случаем будет декодирование текста. У вас есть очевидный случайный массив символов, которые вы также знаете, передают сообщение тем, у кого есть ключ дешифрования. Скажем, что отправитель использовал ключ слева, а ваш Hello World читал: Gwkki Qieks. Решение "большого молотка, без мозгов" создало бы все комбинации для этих букв: от Aaaa до Zzzz, а затем и поиск словарного словаря, чтобы определить, какие слова действительны, и совместно использовать две общие буквы в cypher (i, k) в в той же позиции. Эта функция преобразования - это то, что принимает значение Big O!

Ответ 13

Я думаю, что людей отбрасывают, потому что код не похож на традиционный алгоритм. Вот перевод кода, который более хорошо сформирован, но остается верным духу вопроса OP.

void TrolloWorld(long currentUnixTime, long loopsPerMs){
    long laterUnixTime = 2051222400000;  //unix time of 01/01/2035, 00:00:00
    long numLoops = (laterUnixTime-currentUnixTime)*loopsPerMs;

    for (long i=0; i<numLoops; i++){
        print ("It still not time to print the hello …");
    }
    print("Hello, World!");
}

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

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

Ответ 14

В этот момент времени да

Этот алгоритм имеет неявный ввод, а именно время начала работы программы. Время выполнения будет меняться линейно ¹ в зависимости от того, когда оно будет запущено. В течение 2035 года и после этого цикл while немедленно завершается, и программа заканчивается после постоянных операций ². Поэтому можно сказать, что время выполнения O(max(2035 - start year, 1)) ³. Но поскольку наш начальный год имеет минимальное значение, алгоритм никогда не займет более 20 лет (т.е. Постоянное значение).

Вы можете сделать свой алгоритм более соответствующим вашему намерению, указав DateTime TwentyYearsLater = DateTime.Now + new TimeSpan(365*20,0,0,0); ⁴

¹ Это выполняется для более технического смысла времени выполнения, измеряемого как количество операций, потому что максимальное количество операций на единицу времени. ² Предполагая, что выборка DateTime.Now является постоянной операцией, что является разумным.
³ Я немного злоупотребляю большой записью O, потому что это уменьшающаяся функция по отношению к start year, но мы могли бы легко ее исправить, выразив ее в терминах years prior to 2035.
⁴ Тогда алгоритм больше не зависит от неявного ввода времени начала, но не имеет никакого значения.

Ответ 15

Я бы сказал, что это O (n). используя http://www.cforcoding.com/2009/07/plain-english-explanation-of-big-o.html в качестве ссылки.

Что такое Big O?

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

и

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

добавление; вычитание; умножение; и разделение. Каждый из них операции или проблемы. Метод их решения называется алгоритм.

В вашем примере

с учетом ввода n = 20 (с единицами лет).

алгоритм является математической функцией f(). где f(), как ожидается, будет ждать n лет, при этом строки "debug" между ними. Масштабный коэффициент равен 1. f() можно уменьшить/или увеличить, изменив этот масштабный коэффициент.

для этого случая, выход также равен 20 (изменение входа меняет выход линейно).

по существу функция

f(n) = n*1 = n
    if  n = 20, then 
f(20) = 20