Kann nicht Wachstumsrate um

Question

Ich habe 2 Funktionen, C (n) und A (n)

Ich weiß nicht, warum definieren A (n) ist langsamer als C (n) da höhere Wachstumsrate bedeutet langsamere Laufzeit.

Aus meiner Sicht haben beide Wurzel im Zähler. Jedoch wird A (n) durch logn geteilt, was bedeutet, dass es kleiner als root n sein sollte. Daher wird das ganze A (n) schneller als C (n), da C (n) immer noch die Wurzel n hat (obwohl es n^1/3 ist, aber immer noch die Wurzel hat) und nicht durch irgendetwas geteilt ist.

Gibt es eine sehr einfache Möglichkeit, die Wachstumsrate zu definieren?

Vielen Dank, wenn Sie erklären können, warum A (n) langsamer ist als C (n).

Answer 1

Sowohl C(n) als auch A(n) haben Wurzeln im Zähler, aber sie sind unterschiedliche Wurzeln. In C(n) ist es eine Kubikwurzel und in A(n) ist es eine Quadratwurzel. Eine weitere Möglichkeit, sie zu schreiben wäre:

C(n) = Θ(n^(1/3)) 

und

A(n) = Θ(n^(1/2)/some-log-term) 

Nun ist es klar, dass 1/3 < 1/2 und deshalb mit n groß genug n^(1/3) ist viel weniger als n^(1/2) (und n^(1/2)/some-log-term auch). Tatsächlich ist A(n) beliebig größer, was bedeutet C(n) << A(n)