0
Пример того, когда я бы выбрал алгоритм O (n) над алгоритмом O (1), если для всех n, O (1) быстрее, чем O (n)Выбор O (n) над O (1), когда для всех n, O (1) быстрее, чем O (n)?
A
ответ
0
Один пример - алгоритм O (1) много памяти, а O (n) - нет. И память важнее для вас, чем производительность.
+2
(_Пожалуйста, будьте осторожны с аргументом в нотации для асимптотического поведения функций - _small o_ означает, что _argument строго больше_ - алгоритмы в o (1) должны были бы заканчиваться в строго меньшем, чем постоянное время.) Непараллельный O (1) алгоритм может касаться только O (1) памяти. Ваши рассуждения будут действительны для O (n²) над O (n). – greybeard
+0
@greybeard, я понимаю вашу точку зрения, но я думаю, что этот ответ может быть действительным. Предположим, что оба алгоритма используют O (1) память. Но, o (n) использует 1 байт, а алгоритм o (1) использует 1000 байт. – Arashsoft
+0
Что @greybeard жаловался на случайный способ использования [little-o] (https://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations) вместо [big-O] (https: // en .wikipedia.org/вики/Big_O_notation). Они не * то же самое! –
0
Часто реальные данные поддаются алгоритмам с худшими временными сложностями. Например, сортировка пузырьков, которая работает в O (n^2), часто бывает быстрее по почти отсортированным данным. Зачастую постоянные факторы могут сделать алгоритм слишком медленным, чтобы быть практичным. Помните, что big-O имеет дело с вещами, которые более эффективны в пределе, а не в ближайшем случае. Алгоритм, который равен O (1) с постоянным коэффициентом 10000000, будет значительно медленнее, чем алгоритм O (n) с постоянным коэффициентом 1 для n < 10000000.
+1
Должна быть какая-то часть 'for all of n', которую вы хотите игнорировать. – greybeard
+0
@greybeard мне непонятно, означает ли вопросник, что они * измеряли * алгоритм O (1) по сравнению с O (n), или они просто * предполагают, что O (1) всегда меньше O (n). Это очень плохо сформулированный вопрос. –
+0
(@MarkRansom Я задаю вопрос, чтобы стать заданием вскоре после введения в Big-O-нотацию.) – greybeard
Да, это именно так. – jonrsharpe