命令功能的增长率 [英] Order the growth rate of a function

问题描述

我在回答这个问题时遇到了一些困难.问题是:按增长率对以下各项进行排名:

I have come across some of the difficulties during doing this question. The question is: rank the following by growth rate:

n，√n，log n，log(log n)，log ² n，(1/3) ⁿ ，n！

n, √n, log n, log(log n), log² n, (1/3)ⁿ, n!

上述问题的顺序是什么?我还想知道(一般而言)是否有任何简便的方法可以确定这一点?

What is the order for the above question? I would also like to know if is there any easy way to determine that (in general)?

我对这个问题的回答是

(1/3) ⁿ ⋞log(log n)⋞log n⋞log ² n⋞√n⋞n⋞n！

(1/3)ⁿ ⋞ log(log n) ⋞ log n ⋞ log² n ⋞ √n ⋞ n ⋞ n!

对吗?

推荐答案

您必须学习大的O表示法.

You have to learn big O notation.

这与乘幂排名有关...您可以拥有:

it's all about exponentiation ranking... you can have:

• 1个常数(exp n ^ 0)
• 2个对数(exp n = 1/c)
• 3个线性(exp n ^ 1)
• 4个系数(exp n ^ c)
• 5个指数(exp c ^ n)
• 6阶乘(exp n！)

这是基本规则.从长远来看，每个人都赢"与较低的人(例如，规则5胜过4,3,2和1)

that's the basic rule. On the long run each one "wins" against the lower ones (e.g. rule 5 wins over 4,3,2 and 1)

使用此原理，很容易对从渐近最慢增长到最快增长的函数进行排序:

Using this principle, it is easy to order the functions given from asymptotically slowest-growing to fastest-growing:

1. (1/3)^ n-这是一个常数！ O(1)
2. log(log n)-日志的日志必须比线性函数的log慢.
3. 登录n
4. log ^ 2 n
5. √n-n ^(1/3)，次线性，但比任何对数快
6. n-线性是一阶多项式
7. n！ -阶乘的增长速度快于任何指数.

这篇关于命令功能的增长率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！