Вот есть некий массив, который нужно сортировать. Так же, есть время, за которое массив можно отсортировать. Например, один из самых эффективных это алгоритм, который работает за
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;
}
Но ведь в этой реализации нет никакой константы, или я что то недопонимаю?
