Как вычисляется математическая оценка Big O для сортировки?

Question

Может кто-нибудь объяснить простым языком, как его рассчитать?
Я знаю, что вам нужно посетить n+2+(n-1)+2+...+2+2 элементов, но как вы получите 1/2n^2 + 5/2n - 3? Спасибо!

Answer 1

n + 2 + (n - 1) + 2 + ... + 2 + 2 равно (n + 2) + (n + 1) + ... + 4.Это арифметическая прогрессия , и ее сумма рассчитывается как (n + 2 + 4) * (n + 2 - 4 + 1) / 2.Он равен (n + 6) * (n - 1) / 2 и, наконец, 1/2 * n^2 + 5/2 * n - 3.

f(n) = O(g(n)) означает, что существует такая постоянная C, что f(n) <= C * g(n) для всех достаточно больших n.Если n считается натуральным числом, то, например, 1/2 * n^2 + 5/2 * n - 3 = O(n^2) с C = 3/2.