Сравнение сложности Big O с n ^ 0.000001 и log (n) и многими другими

Question

Я пытался понять сложность Big O, и я прочитал несколько ресурсов, включая ответ dheeran с графиком. Полиномиальное время и экспоненциальное время

У меня мало собственных сомнений и возникает несколько новых сомнений после прочтения ответа ниже, потому что он не был описательным и ясным.

Примечание : n большое (в миллиардах)

Q1. Я читал, что для любого c> 0 log n равен O (n ^ c). Я понимаю, что Big O log n всегда будет меньше n ^ c для любого значения c. Итак, проверьте этот пример:

c = 0,000001

n = 1 000 000 000, т. Е. 1 миллиард

=> n ^ c = 1,00002072348

=> log (1 млрд) = 9

Итак, как получается log n> n ^ c, когда log n равно O (n ^ c)

Q.2 Как упоминалось в ответ, порядок увеличения сложности:

O (1), O (log n), O ((log n) ^ c), O (n), O (n ^ 2) , O (n ^ c), O (c ^ n), O (n!)

Если 0

-O (log n), O ((log n) ^ c)

-O (n ^ c), O (c ^ n)

-O (n), O (c ^ n)

Answer 1

Здесь «в миллиардах» означает достаточно большой. Следовательно, это зависит от функций. Чтобы доказать, что вам нужен n0, он может быть 10^20 здесь, в вашем примере. Кроме того, поскольку c является константой, вы можете выбрать n0 на основе значения c. Например, если c < 1, вы можете выбрать n0 = 10^{10/c}. Таким образом, для всех n > n0, n^c больше, чем log(n).

Для второго вопроса, безусловно, для 0 < c <= 1, c^n меньше, чем все, так как он равен нулю для больше n! и log(n)^c находится в O(log(n)). Поэтому порядок:

c^n, 1, (log(n))^c, log(n), n^c, n, n^2, n!