按增长率由小至大的顺序排列下列各函数_数据结构学习狂人

个人资料

微博

正文字体大小：大中小

按增长率由小至大的顺序排列下列各函数

(2007-03-04 23:05:24)

2¹⁰⁰, (3/2)ⁿ，(2/3)ⁿ， nⁿ ,n^0.5 , n! ，2ⁿ ，lgn ,n^lgn, n^(3/2)

解题策略：常见的时间复杂度按数量级递增排列,依次为:

（《1》先将题中的函数分成如下几类：）

常数阶 0(1) 2¹⁰⁰

对数阶 0(log₂n) lgn

线性阶 0(n)

线性对数阶 0(nlog₂n)

平方阶 0(n²)

立方阶 0(n³)

k次方阶 0(n^k) n^0.5、n^(3/2)

指数阶 0(2ⁿ) n^lgn、(3/2)ⁿ、2ⁿ、 n!、 nⁿ

<2>注意：(2/3)^ⁿ由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。

所以根据以上分析按增长率由小至大的顺序可排列如下：
(2/3)ⁿ < 2¹⁰⁰ < lgn < n^0.5 < n^(3/2) < n^lgn < (3/2)ⁿ < 2ⁿ < n! < nⁿ

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report