複雜度筆記

○(n)   :  f(n) <= c*g(n)           bigO最多會執行幾次

       

Ω(n)   :  f(n) >= c*g(n)           Omega最少會執行幾次

Θ(n)   :  c1*g(n)<=f(n) <= c2*g(n)  theta執行次數會被夾在範圍內

Ex:

     3n+2
          可知bigO是○(n)，知道g(n)=n，代表意思 3n+2<=c*n其中C=4且n>=2。

EX:

A程式的時間複雜度是T1(N)

B程式的時間複雜度是T2(N)

                 A做完接著做B，整體的BIGO=MAX( T1(N) , T2(N) )

         A內呼叫B做遞迴，整體的BIGO=T1(N)*T2(N)

常用的大小表：C < LOGN < LOG^2 N < N < NLOGN < N^2 < N^3 <2^N