Временная сложность: как мы находим O (n ^ 3)?

Question

Я знаю, f(n) = 3*n^3 + 4*n + 2 имеет сложность O (n ^ 3), но я хочу знать, как рассчитать его, используя определение большого O:

If f(n) has complexity O(g(n)), that means there exists a constant c > 0, n0 >=1 where f(n) < c*g(n)

Но как вы определяете, что такое c а что такое g(n)?

Answer 1

Вы можете использовать любой грязный хак, который хотите, чтобы угадать c и n0, которые сработают, а затем доказать их (индукция обычно работает хорошо, но иногда это не нужно).

Здесь просто отметьте, что для n > = 1, n ^ 3> = n> = 1, поэтому

f(n) = 3*n^3 + 4*n + 2
    <= 3*n^3 + 4*n^3 + 2*n^3
     = 9n^3

Это говорит нам о том, что выбор n0 = 1 и c = 9 работает. Здесь мы знали границы и хотели найти константы для проверки; если бы мы не знали границы, мы могли бы угадать ее на основе формулы или выписать некоторые термины.