O(n/2) - можно ли не учитывать знаменатель?
Слышал такое мнение, что коэффициент при n при описании сложности алгоритма можно не учитывать. Правда ли это?
Я считаю, что это мнение ошибочно, поскольку (особенно на больших входных данных) разница между O(n/2) и O(n) будет довольно существенна.
Ответы (1 шт):
Да, это правда. Константные множители игнорируются при описании сложности алгоритмов, будь они даже миллион или наоборот, очень маленькие. При достаточно большом размере данных алгоритм с лучшей сложностью обгонит алгоритм с худшей сложностью с намного меньшей константой.
Конечно, они оказывают влияние на практическую производительность, и некоторые теоретически самые быстрые алгоритмы на практике уступают алгоритмам с худшей сложностью, поскольку размеры данных, на которых они выиграют, не используются или просто нереальны.