Как посчитать время работы алгоритма ( Big O )?

Question

[Гектор Синхром]

Есть алгоритм. Нужно подсчитать "примерное время работы алгоритма". То есть не "засечь время вначале работы и посмотреть на результат" - а нужно "проанализировать алгоритм и сказать примерное время работы (при определённых входных параметрах)".
Начал читать про Big O, но так и не могу понять. Снизу алгоритм сортировки. Как я понял - это O(n^2), потому что цикл вложен в цикл. По логике: f(n) = n^2. К примеру если массив имеет 100 элементов - получается f(100) = 10000. И что мне это даёт? Как мне время найти?

private void Sorting (int[] arraySort)
        {
            for (int i = 0; i < arraySort.Length; i++)
            {
                int minID = i;
                for (int j = i; j < arraySort.Length; j++)
                {
                    if (arraySort[minID] > arraySort[j])
                    {
                        minID = j;
                    }
                }
                int temp = arraySort[i];
                arraySort[i] = arraySort[minID];
                arraySort[minID] = temp;
            }
        }

Comments

[Василий Банников]

1. Big-O считает не скорость алгоритма, а асимптотику.
2. тут кажется будет nlog(n), а не n^2, тк второй цикл идёт не по всему массиву, а только по части

[Гектор Синхром]

Василий Банников, а ВРЕМЯ как мне вычислить?????

[Василий Банников]

Гектор Синхром, время никак. Тольно бенчмарками

[Wataru]

Василий Банников, Нет, тут O(n^2). Если аккуратно подсчитать количество операций сравнения, то их будет что-то порадка N^2/2, потому что там получается сумма N+(N-1)+(N-2)+...+1.

[Василий Банников]

Wataru, ок, никогда не был силён в угадывании.

Answer 1

[GruMouse]

у АЛГОРИТМА нет времени работы, есть число операций(среднее, худшее....)
время работы ПРОГРАММЫ будет зависеть от
скорости процессора/памяти/кэшей
типа процессора/памяти/кэшей
настроек компилятора,ОС,объёмов памяти,
притом не линейно. т.е. если перестанет "хватать" памяти то скорость резко упадёт

Биг О даёт понимание что при сортировать массив в 1.000.000 элементов бесполезно таким способом
ну и если сортировка 1000 эл заняла 1минуту, то 2000 скорей всего будет 4