Big O notation

Big O notation入門

Big O簡介

計算機的計算過程中，基本上都是一些複雜的計算，數以千計，數以萬計或是數以億計的計算，
那麼如何計算和總結為讓我們更加簡單易懂的語言呢，與成績分層是一個道理，A是好的，B次好等等等等，就引入了big O notation這個概念。

程序員如果要進行編程，我們不希望計算機花費大量的時間去進行一個運算，要盡全力將big O 弄到最小。

• 1，2，3，4，5，6，7的是O(1)，是屬於常數的
• n，2n，2n+1，4m+4的是O(n)，是屬於線性函數
• n^2 4 n^2+3等等的話就是O(n^2)，二次的線性函數

如果一個函數它是以多項式來表示：

當我們要看一個多項式的時候，General rule，pick the term that grows the fastest and remove
the constants from it:
5n + 2log(n) ＝O(n).
3n^3 +2^n/6＝ O(2^n ).
8log(n) + 7n ＝ O(n).

Big O範例

O(1)

def isFirstElementNull(elements, value):
return elements[0] == value
#print isFirstElementNull(["1","2"],"1")

無論輸入參數是什麼，這個函數就只執行一次，所以它的複雜度為O(1)。

O(N)

def containsValue(elements, value):
for e in elements:
if e == value:
return True
return False
#print isFirstElementNull(["1","2"],"1")

這裡有一個for循環，如果運氣好就執行一次（elements裡第一個值就跟value一樣），運氣不好就要執行N次（N等於elements的長度，碰巧elements裡最後一個值跟value一樣） ，因為Big O是表示最壞時情形，所以這個函數的複雜度為O(N)。

O( N2)

def containsDuplicates(elements):
for m in range(len(elements)):
for n in range(len(elements)):
if (m != n) and elements[m] == elements[n]:
return True
return False
#print containsDuplicates(["1","2","3","2"])

這裡有兩個嵌套的for循環，所以執行最多的次數肯定為兩個for循環次數相乘，即N*N（N等於elements長度），所以這個函數的複雜度為O(N2)。

O( 2N)

def fibonacci(num):
if num < 2:
return num
return fibonacci(num - 2) + fibonacci(num - 1)
#print fibonacci(5)

這是計算斐波那契數的函數，用遞歸方式實現，執行2的N次方，所以這個函數的複雜度為O(2N)。

O(logN)
log複習
1.底數為10時，寫為lg；
2.底數為e時，稱為自然對數寫為ln,這個在高等數學中用的很多；
3.底數為2時，主要用在計算機中，寫為log，也就是不寫底數；

所以logN其實就是log2n
以Binary Search（也叫拆半查詢和二分查詢）為例，感覺查詢過程就跟切西瓜一樣，先中間切一刀，然後選一塊，再在選定的半個西瓜上再來一刀，再決定選哪塊，再切再選，最後找到滿意的，即1/2,1/4,1/8,1/16…這樣下去。以下是算法腳本

public int binarySearch(int array[],int key) {
int begin = 0;
int end = array.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (array[mid] > key){
end = mid - 1;
}
else if (array[mid] < key){
begin = mid + 1;
}else{
return mid;
}
}
return -1;
}

以下是測試程序

int[] a1 = {1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,100};
int result = binarySearch(a1, 4);
System.out.println(result);
//output: 3

其實這樣一刀一刀的找就是2的倍數關係，比如切了3刀找到，那就有8塊了（其實是4塊，因為你只切選中的那一塊，但為了計算方便，我們就當把西瓜都切了），即2的3次方，如果切5刀找打，那就有32塊，即2的5次方，所以這個算法的時間複雜度就是O(log2N)，即O(logN)。

注意，時間複雜度是個近似值，比如O(2N)就是O(N)，O(3N+5)就是O(N)，這個值要表達的是個複雜度趨勢，記住這點很重要。

複雜度比較

由快到慢
log log n
log n (logarithmic)
sqrt n
n (linear)
n log（n）
n^2 (quadratic)
n^3 (cubic)
…
n^k (polynomial hierarchy)
a^n (exponential hierarchy)
n!

Big O總結

原文：https://www.interviewcake.com/article/python/big-o-notation-time-and-space-complexity?section=algorithmic-thinking&course=fc1

目的:

The Big O notation is the language we use for talking about how long an algorithm takes to run.
O表達式是一種我們用描述一個算法運行中耗時多少的語言表達方式。

詳細描述:

with big o notation we express the runtime in terms of - brace youself - how quickly it grows relative to the input.
我們使用O表達式，相對輸入的增長速度來描述運行時。

從如下幾個方面闡述：

1. how quickly the runtime grows(運行時的增長速度)
   我們很難求出一個算法的真正的運行時間，因為這個跟處理器的處理效率，計算機如何運行等等因素相關，相對於直接使用運行時間表示算法優劣，O表達式是描述運行時的增長速度。
2. relative to the input(相對於輸入)
   如果我們直接計算運行時間，那麼我們可以使用秒來描述速度；當我們計算運行時的增長速度，我們需要基於其他的東西來描述我們的速度，對於O表達式，我們使用輸入的大小，通常稱為n。
3. as the input gets arbitrarily large(輸入變得任意大)
   當n比較小的時候，我們的算法中一些步驟顯的比較重要（耗時佔比大），但當n很大時，這些步驟就不值得一提了。我們最關心的時隨著輸入增大而增長最快的東西，當n非常大的時候，其他東西就很不值得一提了。（漸進線）

其他注意點

1. n could be the actual input, or the size of input(n可能是輸入的值，也可能是輸入的大小)
2. Drop the constants(刪除常量)
3. Drop the less significant terms(刪除一些不重要的條款)
4. We usually talking about the “worse case”(我們經常討論最壞情況)

   有時最壞情況比最好情況要壞的多，面試的時候，也可以通過明確的表述最壞情況，來打動面試官。

5. Space complexity(空間複雜性)：the final frontier(最後的邊界)

   有時候，對於花費更短時間，我們更希望使用更少的存儲空間。討論空間複雜和上面討論時間複雜很相似，都是相對於輸入而言。 當我們討論空間複雜性時，一般討論的是額外增加的空間；對於輸入佔用不考慮。 時間複雜性和空間複雜性，在設計算法時，應進行權衡利弊。

6. Big O analysis is awesome expect it is not(Big O分析很棒，除了它不是)
   使用Big O分析時，也要注意如下幾點，並不是嚴格的按照上面的注意點而行，需進行甄別。

   Big O強調忽略常量，但常量有時也很重要(可以達到很好的優化效果)；
   注意避免過早優化
   有時優化時間或空間對可讀性或編碼時間有負面影響，對於一些初創或代碼開發初期，編寫易於快速發布和易讀的代碼更為重要，儘管運行時間不及預期。

延伸閱讀：
Complexity and Big-O Notation

reference：

• https://blog.csdn.net/uestcyms/article/details/83048225
• https://blog.csdn.net/u013152895/article/details/44115663