Что значит, что алгоритм работает...?

Question

[widget_pro]

Вот есть некий массив, который нужно сортировать. Так же, есть время, за которое массив можно отсортировать. Например, один из самых эффективных это алгоритм, который работает за O(log2n * n), где n - количество элементов массива.
Исходя из этого утверждения, у меня возник вопрос. Как из времени работы алгоритмаO(log2n * n), вычислить время. Допустим, одна итерация происходит за 1мс, количество элементов массива - 16. Подставив в эту формулу число 16 получаем. O(log2(16) * 16) = 64. Значит ли цифра 64 то, что алгоритм выполнится за 64мс?
Так же, погуглив, я выцепил из одной статьи такое выржение

Сложность алгоритма O(n log n) означает, что при больших n время работы алгоритма (или общее количество операций) не более чем C · n log n, где C — некая положительная константа.

. В этом же выражении, я не совсем понимаю, откуда взялась константа C. Вот есть у нас сортировка Хоара, которая работает за O(n log n), так же есть массив и собственно его реализация на js

function partition(items, left, right) {
    var pivot   = items[Math.floor((right + left) / 2)],
        i       = left,
        j       = right;
    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(items, i, j);
            i++;
            j--;
        }
    }
    return i;
}

Но ведь в этой реализации нет никакой константы, или я что то недопонимаю?

Comments

[Василий Дёмин]

Из асимптотической сложности время никак не получить, она показывает сколько операций (в данном случае сравнений) придётся произвести для выполнения алгоритма. Время можно получить, прогнав алгоритм на реальном железе. От языка к языку, от компьютера к компьютеру и от запуска к запуску оно может отличаться.

Answer 1

[dmshar]

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

Answer 2

[Wataru]

Константа вылезает из деталей реализации операций. Вот сортировка пузырьком делает ровно n(n-1)/2 сравнения и помен в худшем случае. Еще столько же операций инкремента счетчика индекса, столько же проверок на конец цикла. Плюс еще n операций для внешнего цикла. И все это O(n^2). Хотя там есть есть /2 и операций четыре типа. И они еще разное время занимают. Скажем, проверки занимают 10 тактов, а инкрименты - 1. Но вся эта мишура не влияет на скорость роста и прячется в константе. Если все сложить. То будет C*n^2 +C2*n+C3 тактов на алгоритм.