Пример, когда я бы выбрал алгоритм O (n) вместо алгоритма O (1), если для всех n, O (1) быстрее, чем O (n)
Выбор O (n) вместо O (1), когда для всех n, O (1) быстрее, чем O (n)?
comment
Да, именно тогда.
- person jonrsharpe schedule 27.10.2016
Ответы (2)
Часто реальные данные поддаются алгоритмам с большей временной сложностью. Например, пузырьковая сортировка, которая выполняется за время O (n ^ 2), часто выполняется быстрее для почти отсортированных данных. Часто постоянные коэффициенты могут сделать алгоритм слишком медленным, чтобы его можно было применить на практике. Помните, что big-O имеет дело с вещами, которые более эффективны в пределе, а не в непосредственном случае. Алгоритм O (1) с постоянным коэффициентом 10000000 будет значительно медленнее, чем алгоритм O (n) с постоянным коэффициентом 1 для n ‹10000000.
person
superlizardmo
schedule
27.10.2016
Должна быть какая-то часть
for all of n, которую вы решите игнорировать.
- person greybeard; 28.10.2016
@greybeard мне не ясно, означает ли спрашивающий, что они измерили алгоритм O (1) по сравнению с алгоритмом O (n), или они просто предполагают O (1) всегда меньше O (n). Это очень неудачно сформулированный вопрос.
- person Mark Ransom; 28.10.2016
(@MarkRansom Я считаю, что вопрос будет заданием вскоре после введения в нотацию Big-O.)
- person greybeard; 28.10.2016
Один из примеров - алгоритм O (1) потребляет много памяти, а алгоритм O (n) - нет. А память для вас важнее производительности.
person
Arashsoft
schedule
27.10.2016
(Пожалуйста, будьте осторожны с регистром в обозначениях для асимптотического поведения функций - маленький o означает, что аргумент строго больше - алгоритмы в o (1) должен завершиться за строго меньшее, чем постоянное время.) Непараллельный алгоритм O (1) может касаться только памяти O (1). Ваше рассуждение будет справедливо для O (n²) над O (n).
- person greybeard; 28.10.2016
@greybeard, я понимаю вашу точку зрения, но думаю, что этот ответ может быть верным. Предположим, что оба алгоритма используют память O (1). Но o (n) использует 1 байт, а алгоритм o (1) использует 1000 байт.
- person Arashsoft; 28.10.2016
На что @greybeard жаловался, так это на то, что вы использовали вместо него маленькую фигню. из big-O. Это не одно и то же!
- person Mark Ransom; 28.10.2016
@MarkRansom, спасибо я исправил
- person Arashsoft; 28.10.2016
