作者MMaze (Maze)
看板Math
标题[其他] 关於时间复杂度（big O）的排序
时间Sat Dec 11 14:34:42 2021
大家好，想请教大家一题关於执行程式时，各函数的时间复杂度的排序。
题目将以下所有函数依照时间复杂度O排序，由大到小:
・N^2 + logN
・2^(2^N)
・NlogN
・lnN
・(n+1)!
・lg(lgN)
・n^3
・n!
・(3/2)^N
・2^(logN)
以下是我的排序，时间复杂度最大排到最小的
1. N! , (N+1)! ----这两个相等 都是O(N)
2. 2^(2^N) ----比O(C^N)又更大
3. (3/2)^N ----O(C^N) (Exponential)
4. 2^(logN) ----比O(C^N)小因为是指数是放logN
5. n^3 ----O(N^3)
6. N^2 + logN ----O(N^2)
7. NlogN ----O(NlogN)
8. lnN ----O(logN)
9. lg(lgN) ----O(loglogN)
想问大家以上的排序正不正确?
我最主要的疑惑是 2^(2^N) , (3/2)^N , 2^(logN) 这三个，
他们都是Exponential的成长速度，但因为指数部分又有包含N在内变数，
所以应该是要照我的排序，还是其实他们三个的时间复杂度都一样呢?
谢谢!
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 103.232.136.184 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1639204484.A.AC6.html
1F：推 bigbigloser : 如果是以2为底，2^(log(N))就是N 12/11 15:43
2F：→ bigbigloser : 然後2^(2^N)比N!大才对(一项一项比较) 12/11 15:46
3F：→ MMaze : to楼上，如果非２为底呢？ 12/11 16:12
4F：→ MMaze : 另外，为什麽2^(2^N)比N!大？阶乘不是复杂度最高吗? 12/11 16:12
5F：推 tsoahans : 两边取log比 log(N!)<NlogN<N^2<2^N=log(2^(2^N)) 12/11 18:06
6F：推 usir166 : 你每项後面用的是big o notation，可以去看一下定义 12/11 20:35
7F：→ usir166 : big-o是函数渐进的上界，因此一个函数的big-O表达 12/11 20:37
8F：→ usir166 : 并不唯一，而即使big-O一样的不同函数时间复杂度也 12/11 20:39
9F：→ usir166 : 不一定会一样，而向一些常见的big-O notation分类如 12/11 20:40
10F：→ usir166 : logn,n,n^2,2^n,n!等等，是因为常用，而不是一定只 12/11 20:41
11F：→ usir166 : 能用这几种分类 12/11 20:43
12F：→ bigbigloser : a^(log(b))=b^(log(a))，2^(2^N)=2*2^(1+2+...+2^(N 12/11 22:03
13F：→ bigbigloser : -1)) 12/11 22:04