Цитата(bems @ 19.6.2010, 19:40  ) |
| это О(2n). Нет? |
И нет, и да.
Смысл O-символики при оценке сложности алгоритма (во всех других случаях, впрочем, тоже) в том, что если количество операций алгоритма зависит от n как f(n), то сложность алгоритма O(g(n)) должна быть такой, чтобы предел f(n)/g(n) при n, стремящемся к бесконечности, оказался ненулевым и конечным.Как следствие, O(n) и O(2*n) попросту ничем не отличаются (и второй вариант при описании асимптотической сложности алгоритмов не используется). Это, кстати, логично не только с формальной точки зрения: поскольку мы не знаем точно, какое количество тактов процессора будет использовано для выполнения той или иной операции, то сравнивать линейные по n алгоритмы по коэффициенту малоосмысленно - вполне возможно, что какой-либо "однопроходный" алгоритм за счет большей трудоемкости обработки одной ячейки массива будет выполняться дольше, чем мой "двупроходный".
Другое дело, что бывают случаи, когда для алгоритма, например, с O(n^3) для некоторого диапазона n на некоторой определенной архитектуре можно получить более быструю реализацию, чем для другого алгоритма с O(n^2), но это уже совсем другая задача, для которой нужно конкретизировать и "стоимость" элементарных операций, и максимальные n, для которых нужно найти эффективное решение.