目錄

一，二分法與大O表示法

1.1寫在前面

1.2需要具備的知識

1.3二分法

1.4更佳的查找方式

1.4.1代碼設計

1.4.2運行時間

1.5大O表示法

1.5.1演算法的運行時間以不同的速度增加

1.5.3一些常見的大O運行時間

一，二分法與大O表示法

1.1寫在前面

從今天開始，我將開始更新演算法圖解入門，也是自己在不斷的學習中總結經驗，感興趣的可以點個關注，有時間就會更新演算法相關的知識點，可能在十天內就可以完成更新，你的每一個點贊和收藏都是我最大的動力，文字和圖片內容部分參考《演算法圖解》這本書，

1.2需要具備的知識

要學會演算法，需要具備基本的代數知識，具體地說，給定函式f(x) = x*2,f(5)的值是多少？如果你的答案是10，那就夠了，

另外，如果你熟悉一門編程語言，演算法將會更容易理解，你可以選擇C語言，也可以選擇Python,也可以是其他語言，

1.3二分法

假設要在電話簿中找一個名字以K打頭的人, (現在誰還用電話簿!)可以從頭開始翻頁,直到進入以K打頭的部分，但你很可能不這樣做,而是從中間開始,因為你知道以K打頭的名字在電話簿中間，
又假設要在字典中找一個以S打頭的單詞,你也將從中間附近開始.現在假設你登錄QQ當你這樣做時, QQ必須核實你是否有其網站的賬戶,因此必須在其資料庫中查找你的用戶名，如果你的用戶名為karlmageddon, QQ可從以A打頭的部分開始查找,但更合乎邏輯的做法是從中間開始查找，
這是一個查找問題,在前述所有情況下,都可使用同一種演算法來解決問題,這種演算法就是二分查找，

下面舉一個例子說明二分查找的作業原理，我隨便想一個1~100的數字

你的目標是以最少的次數找到該數字，你每次猜測后，我會說小了，大了或者對了，

這是簡單查找，更準確的應該是傻找，每次猜測只能排除一個數字，如果我想找99，要猜99次才能得到結果，

1.4更佳的查找方式

從50開始，每次判斷與50的大小，沒有猜對，但排除了一半的數字，猜75，大了，將余下的數字排除一半，一直猜，最后猜到了53.

這是二分查找，是我們學習的第一種演算法！每次猜測的數字如下，100個元素最多用7步，

如果查找的單詞位于字典的末尾，使用簡單查找要240000步，用二分查找是最多用18步，

1.4.1代碼設計

給定一個陣列arr[] = {1,2,3,4,5,6,7,8,9} 剛開始給定 left = 1， right = 9 ， 那么mid = 5
例如要找的是3，3在mid的左邊，那么讓left向右走一步（left++），這時候right也得重新給 （right = mid -1），再重新計算mid值，如果還是沒找到繼續重復步驟直至找到為止，

int main()
{
	int n = 0;
	int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	int sz = sizeof(arr) / sizeof(arr[0]);//求陣列個數
	scanf("%d", &n);//輸入要找的數
	int getchar（）;
	int left = 0;
	int right = sz - 1;
	while (left < right)
	{
		int mid = (left + right) / 2;
		if (n < arr[mid])
		{
			right = mid - 1;
		}
		else if (n>arr[mid])
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了是： %d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到了");
	}
	return 0;
}

1.4.2運行時間

每次介紹演算法時,我都將討論其運行時間，一般而言,應選擇效率最高的演算法,以最大限度地減少運行時間或占用空間，
回到前面的二分查找，使用它可節省多少時間呢?簡單查找逐個地檢查數字,如果串列包含100個數字,最多需要猜100次，如果串列包含40億個數字,最多需要猜40億次，換言之,最多需要猜測的次數與串列長度相同,這被稱為線性時間 (linear time)，
二分查找則不同，如果串列包含100個元素,最多要猜7次;如果串列包含40億個數字,最多需猜32次，厲害吧?二分查找的運行時間為對數時間(或log時間)，下表總結了我們發現的情況，

1.5大O表示法

大O表示法是一種特殊的表示方法，指出了演算法的速度有多快，

1.5.1演算法的運行時間以不同的速度增加

Bob要為NASA撰寫一個查找演算法,這個演算法在火箭即將登陸月球前開始執行,幫助計算著陸地點，
這個示例表明,兩種演算法的運行時間呈現不同的增速，Bob需要做出決定,是使用簡單查找還是二分查找，使用的演算法必須快速而準確，
一方面,二分查找的速度更快，Bob必須在10秒鐘內找出著陸地點,否則火箭將偏離方向，另一方面,簡單查找演算法撰寫起來更容易,因此出現bug的可能性更小，Bob可不希望引導火箭著陸的代碼中有bug!為確保萬無一失, Bob決定計算兩種演算法在串列包含100個元素的情況下需要的時間，
假設檢查一個元素需要1毫秒，使用簡單查找時, Bob必須檢查100個元素,因此需要100毫秒才能查找完畢，而使用二分查找時,只需檢查7個元素(l0g2100大約為7),因此需要7毫秒就能查找完畢，然而,實際要查找的串列可能包含10億個元素,在這種情況下,簡單查找需要多長時間呢?二分查找又需要多長時間呢?請務必找出這兩個問題的答案,再接著往下讀，

Bob使用包含10億個元素的串列運行二分查找,運行時間為30毫秒( 1og 1 000 000 000約為30),他心里想,二分查找的速度大約為簡單查找的15倍,因為串列包含100個元素時,簡單查找需要100毫秒,而二分查找需要7毫秒，因此,串列包含10億個元素時,簡單查找需要30 x 15=450毫秒,完全符合在10秒內查找完畢的要求，Bob決定使用簡單查找，這是正確的選擇嗎?
不是，實際上, Bob錯了,而且錯得離譜，串列包含10億個元素時,簡單查找需要10億毫秒相當于11天!為什么會這樣呢?因為二分查找和簡單查找的運行時間的增速不同，

也就是說，隨著元素的增加，二分法所查找的額外時間并不多，

1.5.2大O表示法指出了最糟糕情況夏下的運行時間

假設你使用簡單查找在電話簿中找人，你知道,簡單查找的運行時間為O(n),這意味著在最糟糕情況下,必須查看電話簿中的每個條目，如果要查找的是Adit-電話簿中的第一個人,一次就能找到,無需查看每個條目，考慮到一次就找到了Adit,請問這種演算法的運行時間是O(n)還是O(1)呢？
簡單查找的運行時間總是為(n)，在找Adi時,一次就找到了,這是最佳的情形,但大O表示法說的是最糟的情形，因此,你可以說,在最糟情況下,必須查看電話簿中的每個條目,對應的運行時間為O(n),這是一個保證--你知道簡單查找的運行時間不可能超過O(n)，

1.5.3一些常見的大O運行時間

下面按從快到慢的順序列出了你經常會遇到的5種大O運行時間，
1,O(log n),也叫對數時間,這樣的演算法包括二分查找，
2,O(n),也叫線性時間,這樣的演算法包括簡單查找，
3,O(n * log n),這樣的演算法是快速排序--一種速度較快的排序演算法，
4,O(n^2)這樣的演算法是選擇排序--種速度較慢的排序演算法，
5,O(n!),這樣的演算法包括接下來將介紹的旅行商問題的解決方案-種非常慢的演算法，
假設你要繪制一個包含16格的網格,且有5種不同的演算法可供選擇,這些演算法的運行時間如上所示，如果你選擇第一種演算法,繪制該網格所需的運算元將為4 ( log 16=4),，假設你每秒可執行10次操作,那么繪制該網格需要0.4秒，如果要繪制一個包含1024格的網格呢?這需要執行10( log 1024 = 10 )次操作,換言之,繪制這樣的網格需要1秒，這是使用第一種演算法的情況，
第二種演算法更慢,其運行時間為O(n)，即要繪制16個格子,需要執行16次操作;要繪制1024個格子,需要執行1024次操作，執行這些操作需要多少秒呢?

從圖中我可以得到啟示

1，演算法的速度并非指的是時間，而是運算元的增長速度，

2，談論演算法速度時，我們說的是隨著輸入的增加，其運行時間將以怎樣的速度增加，

3，演算法的運行時間用大O表示法表示，