O (регистрируют N), == O (1) - Почему нет?

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

I do not believe algorithms where you can freely choose between O(1) with a large constant and O(logN) really exists. If there is N elements to work with at the beginning, it is just plain impossible to make it O(1), the only thing that is possible is move your N to some other part of your code.

What I try to say is that in all real cases I know off you have some space/time tradeoff, or some pre-treatment such as compiling data to a more efficient form.

That is, you do not really go O(1), you just move the N part elsewhere. Either you exchange performance of some part of your code with some memory amount either you exchange performance of one part of your algorithm with another one. To stay sane you should always look at the larger picture.

My point is that if you have N items they can't disappear. In other words you can choose between inefficient O(n^2) algorithms or worse and O(n.logN) : it's a real choice. But you never really go O(1).

What I try to point out is that for every problem and initial data state there is a 'best' algorithm. You can do worse but never better. With some experience you can have a good guessing of what is this intrisic complexity. Then if your overall treatment match that complexity you know you have something. You won't be able to reduce that complexity, but only to move it around.

If problem is O(n) it won't become O(logN) or O(1), you'll merely add some pre-treatment such that the overall complexity is unchanged or worse, and potentially a later step will be improved. Say you want the smaller element of an array, you can search in O(N) or sort the array using any common O(NLogN) sort treatment then have the first using O(1).

Is it a good idea to do that casually ? Only if your problem asked also for second, third, etc. elements. Then your initial problem was truly O(NLogN), not O(N).

And it's not the same if you wait ten times or twenty times longer for your result because you simplified saying O(1) = O(LogN).

I'm waiting for a counter-example ;-) that is any real case where you have choice between O(1) and O(LogN) and where every O(LogN) step won't compare to the O(1). All you can do is take a worse algorithm instead of the natural one or move some heavy treatment to some other part of the larger pictures (pre-computing results, using storage space, etc.)

Assume that in your entire application, one algorithm accounts for 90% of the time the user waits for the most common operation.

Suppose in real time the O(1) operation takes a second on your architecture, and the O(logN) operation is basically .5 seconds * log(N). Well, at this point I'd really like to draw you a graph with an arrow at the intersection of the curve and the line, saying, "It matters right here." You want to use the log(N) op for small datasets and the O(1) op for large datasets, in such a scenario.

Big-O notation and performance optimization is an academic exercise rather than delivering real value to the user for operations that are already cheap, but if it's an expensive operation on a critical path, then you bet it matters!

Правила определения нотации Big-O будут проще, если вы не решите, что O (log n) = O (1).

Как сказал Кшизио , вы можете накопить O (log n) s, и тогда они будут иметь очень заметную разницу. Представьте, что вы выполняете двоичный поиск: O (log n) сравнений, а затем представьте, что сложность каждого сравнения O (log n). Если пренебречь обоими, вы получите O (1) вместо O (log ² n). Точно так же вы можете каким-то образом прийти к O (log ¹⁰ n), и тогда вы заметите большую разницу для не слишком больших «n».

Да, log (N) <100 для большинства практических целей, и Нет, вы не всегда можете заменить его константой.

Например, это может привести к серьезным ошибкам в оценке производительности вашей программы. Если программа O (N) обработала массив из 1000 элементов за 1 мс, тогда вы уверены, что он обработает 10 ⁶ элементов за 1 секунду (или около того). Если же программа O (N * logN), то обработка 10 ⁶ элементов займет ~ 2 секунды. Это различие может иметь решающее значение - например, вы можете подумать, что у вас достаточно мощности сервера, потому что вы получаете 3000 запросов в час и думаете, что ваш сервер может обрабатывать до 3600.

Другой пример. Представьте, что у вас есть функция f (), работающая в O (logN), и на каждой итерации, вызывающей функцию g (), которая также работает в O (logN). Затем, если вы замените оба журнала константами, вы думаете, что ваша программа работает в постоянное время. Однако реальность будет жестокой - два журнала могут дать вам множитель 100 * 100.

то обработка 10 ⁶ элементов займет ~ 2 секунды. Это различие может иметь решающее значение - например, вы можете подумать, что у вас достаточно мощности сервера, потому что вы получаете 3000 запросов в час и думаете, что ваш сервер может обрабатывать до 3600.

Другой пример. Представьте, что у вас есть функция f (), работающая в O (logN), и на каждой итерации, вызывающей функцию g (), которая также работает в O (logN). Затем, если вы замените оба журнала константами, вы думаете, что ваша программа работает в постоянное время. Однако реальность будет жестокой - два журнала могут дать вам множитель 100 * 100.

то обработка 10 ⁶ элементов займет ~ 2 секунды. Это различие может иметь решающее значение - например, вы можете подумать, что у вас достаточно мощности сервера, потому что вы получаете 3000 запросов в час и думаете, что ваш сервер может обрабатывать до 3600.

Другой пример. Представьте, что у вас есть функция f (), работающая в O (logN), и на каждой итерации, вызывающей функцию g (), которая также работает в O (logN). Затем, если вы замените оба журнала константами, вы думаете, что ваша программа работает в постоянное время. Однако реальность будет жестокой - два журнала могут дать вам множитель 100 * 100.

и на каждой итерации вызывается функция g (), которая также работает в O (logN). Затем, если вы замените оба журнала константами, вы думаете, что ваша программа работает в постоянное время. Однако реальность будет жестокой - два журнала могут дать вам множитель 100 * 100.

и на каждой итерации вызывается функция g (), которая также работает в O (logN). Затем, если вы замените оба журнала константами, вы думаете, что ваша программа работает в постоянное время. Однако реальность будет жестокой - два журнала могут дать вам множитель 100 * 100.

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

Все, что вам говорит big-O, является форма этой функции.

• O (1) означает, что существует некоторое число A такое, что f (N)

• O (N) означает, что существует некоторое A такое, что f (N) < AN для большого N.

• O (N ^ 2) означает, что существует A такое, что f (N)

• O (log (N)) означает, что существует A такое, что f (N)

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

Теоретически

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

Я бы сказал, что практическая цель анализа большого О - попытаться предсказать время выполнения вашего алгоритма как можно раньше. насколько возможно. Вы можете упростить анализ, вычеркнув лог (n) терминов, но тогда вы он снизил предсказательную силу оценки.

На практике

Если вы читаете оригинальные статьи Ларри Пейджа и Сергея Брина по архитектуре Google, они говорят об использовании хеш-таблиц для всего, чтобы гарантировать, что, например, поиск кэшированная веб-страница требует только одного поиска на жестком диске. Если вы использовали индексы B-дерева для поиска, вам может потребоваться четыре или пять поисков на жестком диске для выполнения некэшированного поиска [*]. Четырехкратное увеличение требований к дискам для хранения кэшированных веб-страниц заслуживает внимания с точки зрения бизнеса и предсказуемо, если вы не исключите все термины O (log (n)).

PS Извините за использование Google в качестве примера , они похожи на Гитлера в компьютерной версии закона Годвина .

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

PS Извините за использование Google в качестве примера , они похожи на Гитлера в компьютерной версии закона Годвина .

они говорят об использовании хэш-таблиц для всего, чтобы гарантировать, что, например, для поиска кэшированной веб-страницы требуется только один поиск на жестком диске. Если вы использовали индексы B-дерева для поиска, вам может потребоваться четыре или пять поисков на жестком диске для выполнения некэшированного поиска [*]. Четырехкратное увеличение требований к дискам для хранения кэшированных веб-страниц заслуживает внимания с точки зрения бизнеса и предсказуемо, если вы не исключите все термины O (log (n)).

PS Извините за использование Google в качестве примера , они похожи на Гитлера в компьютерной версии закона Годвина .

[*] При условии чтения 4 КБ с диска, 100 млрд веб-страниц в индексе, ~ 16 байт на ключ в узле B-дерева.

O (logN) * ​​O (logN) * ​​O (logN) сильно отличается. O (1) * O (1) * O (1) остается постоянным. Также простой стиль быстрой сортировки O (nlogn) отличается от O (n O (1)) = O (n). Попробуйте отсортировать 1000 и 1000000 элементов. Последнее не в 1000 раз медленнее, это в 2000 раз, потому что log (n ^ 2) = 2log (n)

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

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

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

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

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

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

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

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

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

Что вы имеете в виду, говоря, "имеет ли это значение"?

Если вы столкнулись с выбором алгоритма O (1) и O (lg n) one, то не следует предполагать, что они равны. Вы должны выбрать постоянное время. Почему бы и нет?

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

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

Даже если, как вы говорите, lg (n) < 100 для всех практических целей, это все еще в 100 раз больше ваших других накладных расходов. Если я вызываю вашу функцию N раз, то начинает иметь значение, работает ли ваша функция с логарифмическим временем или константой, потому что общая сложность тогда O (n lg n) или O (n) .

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

Часто вы можете предположить, что логарифмические алгоритмы достаточно быстры , но что вы получаете, считая их постоянными?

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

Затем подумайте, что вы ожидаете, что N будет. Если у вас есть веские основания полагать, что N <10, вы можете использовать линейный поиск вместо двоичного. Это O (N) вместо O (log N), что согласно вашим источникам будет иметь значение, но линейный поиск, который перемещает найденные элементы на передний план, вполне может превзойти более сложное сбалансированное дерево, в зависимости от приложения .

С другой стороны, обратите внимание, что даже если log N вряд ли превысит 50, коэффициент производительности 10 действительно огромен - если вы ограничены вычислительными ресурсами, подобный фактор может легко повлиять на ваше приложение. Если тебе этого мало, ты Я часто вижу в алгоритмах множители (log N) ^ 2 или (logN) ^ 3, поэтому даже если вы думаете, что можете игнорировать один фактор (log N), это не значит, что вы можете игнорировать больше из них.

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

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

В настоящее время существуют практические альтернативные алгоритмы для линейного программирования (с wost-случаем с полиномиальным временем, если это того стоит), которые на практике могут превзойти симплексный метод. Но, в зависимости от проблемы,

Для достаточно маленьких N, O (N ^ N) может на практике заменить на 1. Не O (1) (по определению), но для N = 2 вы можете рассматривать это как одну операцию с 4 частями или операцию с постоянным временем.

Что, если все операции занимают 1 час? Тогда разница между O (log N) и O (1) велика, даже при небольшом N.

Или, если вам нужно запустить алгоритм десять миллионов раз? Хорошо, это заняло 30 минут, поэтому, когда я запускаю его на наборе данных в сто раз большем, он все равно должен занимать 30 минут, потому что O (logN) «то же самое», что и O (1) .... а ... что?

. Ваше утверждение, что «Я понимаю O (f (N))», явно ложно.

Реальные приложения, о ... я не знаю .... КАЖДЫЙ ИСПОЛЬЗОВАНИЕ O () - нотации КОГДА-ЛИБО?

Например, двоичный поиск в отсортированном списке из 10 миллионов элементов. Это та самая ПРИЧИНА, по которой мы используем хеш-таблицы, когда данные становятся достаточно большими. Если вы думаете, что O (logN) - это то же самое, что O (1), тогда зачем вам КОГДА-ЛИБО использовать хэш вместо двоичного дерева?

Равенство, как вы его описываете, является распространенным злоупотреблением обозначениями.

Чтобы уточнить: мы обычно пишем f (x) = O (logN), чтобы подразумевать, что "f (x) is O (logN)".

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

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

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

You asked for a real-world example. I'll give you one. Computational biology. One strand of DNA encoded in ASCII is somewhere on the level of gigabytes in space. A typical database will obviously have many thousands of such strands.

Now, in the case of an indexing/searching algorithm, that log(n) multiple makes a large difference when coupled with constants. The reason why? This is one of the applications where the size of your input is astronomical. Additionally, the input size will always continue to grow.

Admittedly, these type of problems are rare. There are only so many applications this large. In those circumstances, though... it makes a world of difference.

O (log N) может вводить в заблуждение. Возьмем, к примеру, операции с красно-черными деревьями .
Операции O (logN), но довольно сложные, что означает множество операций низкого уровня.

000) раз больше, чем первый вход

, если я запускаю B на входе размера a, то на входе размером 1000000 * a, я могу ожидать, что второй вход займет примерно такое же количество времени, что и первый ввод

РЕДАКТИРОВАТЬ : Подумав еще над вашим вопросом, я действительно думаю, что в нем есть некоторая мудрость. Хотя я бы никогда не сказал, что правильно сказать O (lgN) == O (1), IS возможно, что алгоритм O (lgN) может использоваться вместо алгоритма O (1). Это возвращает нас к пункту об абсолютной производительности выше: просто знание одного алгоритма O (1), а другого алгоритма O (lgN), НЕ достаточно, чтобы объявить, что вы должны использовать O (1) вместо O (lgN), конечно, возможно, учитывая ваш диапазон возможных входов, O (lgN) может вам помочь.

затем на входе размером 1000000 * a я могу ожидать, что второй ввод займет примерно столько же времени, что и первый ввод

РЕДАКТИРОВАТЬ : Поразмыслив над вашим вопросом, я думаю, что есть мудрость в том, чтобы быть в нем. Хотя я бы никогда не сказал, что правильно сказать O (lgN) == O (1), IS возможно, что алгоритм O (lgN) может использоваться вместо алгоритма O (1). Это возвращает нас к пункту об абсолютной производительности выше: просто знание одного алгоритма O (1), а другого алгоритма O (lgN), НЕ достаточно, чтобы объявить, что вы должны использовать O (1) вместо O (lgN), конечно, возможно, учитывая ваш диапазон возможных входов, O (lgN) может вам помочь.

то на входе размером 1000000 * a я могу ожидать, что второй ввод займет примерно столько же времени, что и первый ввод

РЕДАКТИРОВАТЬ : Обдумывая ваш вопрос еще раз, я думаю, что есть мудрость в том, чтобы быть в нем. Хотя я бы никогда не сказал, что правильно сказать O (lgN) == O (1), IS возможно, что алгоритм O (lgN) может использоваться вместо алгоритма O (1). Это возвращает нас к пункту об абсолютной производительности выше: просто знание одного алгоритма O (1), а другого алгоритма O (lgN), НЕ достаточно, чтобы объявить, что вы должны использовать O (1) вместо O (lgN), конечно, возможно, учитывая ваш диапазон возможных входов, O (lgN) может вам помочь.

Обдумывая ваш вопрос еще раз, я думаю, что в нем есть мудрость. Хотя я бы никогда не сказал, что правильно сказать O (lgN) == O (1), IS возможно, что алгоритм O (lgN) может использоваться вместо алгоритма O (1). Это возвращает нас к пункту об абсолютной производительности выше: просто знание одного алгоритма O (1), а другого алгоритма O (lgN), НЕ достаточно, чтобы объявить, что вы должны использовать O (1) вместо O (lgN), конечно, возможно, учитывая ваш диапазон возможных входов, O (lgN) может вам помочь.

Обдумывая ваш вопрос еще раз, я думаю, что в нем есть мудрость. Хотя я бы никогда не сказал, что правильно сказать O (lgN) == O (1), IS возможно, что алгоритм O (lgN) может использоваться вместо алгоритма O (1). Это возвращает нас к пункту об абсолютной производительности выше: просто знание одного алгоритма O (1), а другого алгоритма O (lgN), НЕ достаточно, чтобы объявить, что вы должны использовать O (1) вместо O (lgN), конечно, возможно, учитывая ваш диапазон возможных входов, O (lgN) может вам помочь.

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

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

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

O (1) и O (logn) имеют большое значение, когда вы начинаете комбинировать алгоритмы.

Возьмем, к примеру, объединение с индексами. Если бы вы могли выполнить соединение в O (1) вместо O (logn), вы бы получили огромный прирост производительности. Например, с O (1) вы можете присоединиться любое количество раз, и у вас все еще есть O (1). Но с O (logn) вам нужно каждый раз умножать количество операций на logn.

Для больших входных данных, если у вас уже есть алгоритм, который уже был O (n ^ 2), вы бы предпочли выполнить операцию, которая была O (1) внутри, а не O (logn) внутри.

Также помните, что Big-O чего угодно может иметь постоянные накладные расходы. Допустим, постоянные накладные расходы составляют 1 миллион. При O (1) эти постоянные накладные расходы не увеличивают количество операций так сильно, как O (logn).

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

Название вопроса вводит в заблуждение (хорошо выбрано, чтобы вызвать дебаты, заметьте).

O (log N) == O (1) явно неверно (и плакат знает об этом). Нотация Big O, по определению, относится к асимптотическому анализу. Когда вы видите O (N), N приближается к бесконечности. Если N присваивается константа, это не Big O.

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

Анализ Big O - это круто, потому что он позволяет сравнивать алгоритмы, не увязая в зависимости от платформы. проблемы (размер слов, инструкции на операцию, скорость памяти в зависимости от скорости диска). Когда N стремится к бесконечности, эти проблемы исчезают. Но когда N равно 10000, 1000, 100, эти проблемы, наряду со всеми другими константами, которые мы исключили из функции O, начинают иметь значение.

Чтобы ответить на вопрос автора: O (log N)! = O (1), и вы правы, алгоритмы с O (1) иногда не намного лучше алгоритмов с O (log N), в зависимости от от размера входных данных и всех тех внутренних констант, которые были пропущены при анализе Big O.

Если вы знаете, что собираетесь увеличить N, используйте анализ Big O. В противном случае вам потребуются эмпирические тесты.

Чтобы ответить на вопрос автора: O (log N)! = O (1), и вы правы, алгоритмы с O (1) иногда не намного лучше алгоритмов с O (log N), в зависимости от от размера входных данных и всех тех внутренних констант, которые были пропущены при анализе Big O.

Если вы знаете, что собираетесь увеличить N, используйте анализ Big O. В противном случае вам потребуются эмпирические тесты.

Чтобы ответить на вопрос автора: O (log N)! = O (1), и вы правы, алгоритмы с O (1) иногда не намного лучше алгоритмов с O (log N), в зависимости от от размера входных данных и всех тех внутренних констант, которые были пропущены при анализе Big O.

Если вы знаете, что собираетесь увеличить N, используйте анализ Big O. В противном случае вам потребуются эмпирические тесты.

O (log N) может вводить в заблуждение. Возьмем, например, операции с Красно-Черными деревьями .
Операции O (logN), но довольно сложные, что означает много операций низкого уровня.

, вы правы, во многих случаях это не имеет значения для практических целей. но ключевой вопрос - «как быстро РАСТЕТ N». большинство известных нам алгоритмов принимают размер входных данных, поэтому он линейно увеличивается

, но в некоторых алгоритмах значение N определяется сложным образом. если N - «количество возможных комбинаций лотереи для лотереи с X различными числами», внезапно становится важным, какой у вас алгоритм - O (1) или O (logN)

По моему опыту, единственное, что NHibernate требует от домена, - это виртуальные свойства и методы, а также конструктор по умолчанию без аргументов, который, как сказал Джефф, может быть помечен как закрытый или защищенный, если это необходимо. Вот и все. NHibernate - мой выбор OR / M, и я считаю, что весь стек NHibernate (NHibernate, NHibernate Validator, Fluent NHibernate, LINQ to NHibernate) является наиболее убедительной структурой для сохранения доменов POCO.

Несколько вещей, которые вы можете сделать с NHibernate:

• Украсьте модель своей предметной области атрибутами NHV. Эти константы позволяют вам делать три вещи: проверять ваши объекты, убедитесь, что недопустимые объекты не сохраняются через NHibernate, и помогите автоматически сгенерировать вашу схему при использовании инструментов NHibernate SchemaExport или SchemaUpdate.
• Сопоставьте модель своей предметной области с вашим постоянным хранилищем с помощью Fluent NHibernate. Для меня основным преимуществом использования FNH является возможность автоматически отображать ваши объекты на основе установленных вами соглашений. Кроме того, вы можете при необходимости переопределить эти автоматические приложения, вручную написать карты классов, чтобы получить полный контроль над сопоставлениями, и при необходимости использовать файлы xml hbm.
• После того, как вы купите использование NH, вы можете легко использовать SchemaExport или Инструменты SchemaUpdate для создания и выполнения DDL для вашей базы данных, позволяющие автоматически переносить изменения домена в вашу базу данных при инициализации фабрики сеансов NH. Это позволяет забыть о базе данных, для всех намерений и целей и вместо этого сконцентрируйтесь на своем домене. Обратите внимание: во многих случаях это может оказаться бесполезным или идеальным вариантом, но для быстрой локальной разработки приложений, ориентированных на домен, я считаю это удобным.
• Кроме того, мне нравится использовать общие репозитории для обработки сценариев CRUD. Например, у меня обычно есть IRepository, который определяет методы для получения всех объектов в виде IQueryable, отдельного объекта по идентификатору, для сохранения объекта и для удаления объекта. Для всего остального NH предлагает богатый набор механизмов запросов - вы можете использовать LINQ to NHibernate, HQL, запросы критериев и прямой SQL, если это необходимо.

Единственный компромисс, который вам нужно сделать, - это использовать атрибуты NHV в вашем домене. . Для меня это не препятствие, поскольку NHV - это автономный фреймворк, который добавляет дополнительные возможности, если вы решите использовать NHibernate.

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

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

• при линейном поиске поиск занимает в среднем 1 000 000 000 000 шагов (чрезвычайно заметное изменение)
• при бинарном поиске поиск занимает в среднем 41 шаг (неразличимое изменение)

Как мы видим из этого примера, для всех намерений и целей, алгоритм O (log n) , такой как двоичный поиск, часто неотличим от алгоритма O (1) , такого как всеведение.

Вывод такой: * мы используйте алгоритмы O (log n) , потому что они часто неотличимы от постоянного времени, и потому что они часто работают феноменально лучше, чем алгоритмы с линейным временем.

Очевидно, эти примеры предполагают разумные константы. Очевидно, что это общие наблюдения, которые применимы не ко всем случаям. Очевидно, эти точки относятся к асимптотическому концу кривой, не конец n = 3 .

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