複雜度

複雜度

時間複雜度

衡量一個算法執行所消耗時間的長短

T(n)=O(F(n)) ,T是怎麼随着n的變化而變化的

按複雜度排序：

• 常數階 O(1)
• 對數階 O(logN)
• 線性階 O(n)
• 線性對數階 O(nlogN)
• 平方階 O(n^2)
• 立方階 O(n^3)
• K次方階 O(n^k)
• 指數階 O(2^n)

舉例說明：

1. 常數階O(1)

   無論執行了多少行代碼，隻有是沒有循環等複雜結構，那時間複雜度就是O(1)

   int i=1;
   int j=2;
   ++i;
   j--;
   int s=i+j;
              

2. 對數階O(logN)

   循環x次之後i就大于n了，此時退出循環，那麼n=2x，x=log2n，時間複雜度為O(logN)

   int i=1;
   while(i<n){
       i=i*2;
   }
              

3. 線性階O(n)

   循環次數由n決定，時間複雜度為O(n)

   for(i=1;i<n;++i){
       System.out.print(i);
   }
              

4. 線性對數階O(nlogN)

   在對數階的基礎上再循環n次，時間複雜度就變成了O(nlogN)

   for(m=1;m<n;m++){
       int i=1;
   	while(i<n){
   		i=i*2;
   	}
   }
              

5. 平方階O(n^2)

   兩個線性階嵌套循環，它的時間複雜度就是O(n^2)

   for(x=1;i<=n;x++){
      for(i=1;i<n;++i){
   		System.out.print(i);
   	} 
   }
              

   如果将其中一層循環的n改成m，那它的時間複雜度就變成了O(m*n)
6. 立方階O(n3)，k次方階O(nk)，原理都同平方階，多幾層循環嵌套

空間複雜度

衡量一個算法執行需要占用記憶體空間的多少

S(n)=O(F(n)) ,T是怎麼随着n的變化而變化的

• O(1)
• O(n)
• O(n^2)