命令功能的增长率 [英] 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 2 n,(1/3) n ,n!
n, √n, log n, log(log n), log2 n, (1/3)n, 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) n ⋞log(log n)⋞log n⋞log 2 n⋞√n⋞n⋞n!
(1/3)n ⋞ log(log n) ⋞ log n ⋞ log2 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/3)^ n-这是一个常数! O(1)
- log(log n)-日志的日志必须比线性函数的log慢.
- 登录n
- log ^ 2 n
- √n-n ^(1/3),次线性,但比任何对数快
- n-线性是一阶多项式
- n! -阶乘的增长速度快于任何指数.
这篇关于命令功能的增长率的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!