一、算法簡介
1.1 算法是
-
算法是一組完成任務的指令。任何代碼片段都可視為算法。 - 通過查電話問題了解算法
1. 問題：按字母排序的電話本（有 n 個電話號碼），從中查找出以 k 開頭的某個電話。
2. 問題對應的常用算法有：
簡單查找，按順序一個接一個查，最多需要的步驟是n步；
二分查找，每次過濾一半的值，最多需要的步驟是logn。
log 表示為以2為底的對數(shù)；
1.2 二分查找法 （查找列表必須為有序列表，默認遞增類型）
/**
二分查找（常見邏輯）
@param sourceArray 源有序排列數(shù)數(shù)組
@param searchingNum 要查找的數(shù)
@return 要查找的數(shù)所在數(shù)組的位置索引，沒有則返回-1
*/
+ (NSInteger)binarySearchWithoutRecursion:(NSArray *)sourceArray withSearchingNum:(NSNumber *)searchingNum {
NSInteger low = 0;
NSInteger high = sourceArray.count - 1;
while (low <= high) {
NSInteger middle = low + (high+low)/2;
if (searchingNum.integerValue == [sourceArray[middle] integerValue]) {
return middle;
} else if(searchingNum.integerValue < [sourceArray[middle] integerValue]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
/**
二分查找（使用遞歸方法）
*/
+ (NSInteger)binarySearchWithRecursion:(NSArray *)sourceArray withSearchingNum:(NSNumber *)searchingNum {
NSInteger low = 0;
NSInteger high = sourceArray.count - 1;
return [self binSearch:sourceArray withLow:low withHigh:high withKeyNum:searchingNum];
}
+ (NSInteger)binSearch:(NSArray *)srcArray withLow:(NSInteger)low withHigh:(NSInteger)high withKeyNum:(NSNumber *)keyNum {
if (low <= high) {
NSInteger mid = (low + high)/2;
if (keyNum.integerValue == [srcArray[mid] integerValue]) {
return mid;
} else if([keyNum integerValue] < [srcArray[mid] integerValue]) {
return [self binSearch:srcArray withLow:low withHigh:(mid - 1) withKeyNum:keyNum];
} else {
return [self binSearch:srcArray withLow:mid+1 withHigh:high withKeyNum:keyNum];
}
} else {
return -1;
}
}
1.3 運行時間
說到算法時，都要討論其運行時間，針對不同的算法，我們的選中目的通常是：
選擇效率最高的算法，以最大限度的減少運行時間或占用的空間
如下圖對應著簡單查找 和 二分查找 的運時間：
簡單查找 和 二分查找 的運時間對比
1.4 大 O 表示法
1.4.1 大 O 表示法格式如下：
大 O 表示法格式.png
- 大 O 表示法指出了算法有多快。
- 大 O 表示法指定并非是以秒為單位的速度。
- 大 O 表示法讓你能夠比較操作數(shù)，它指出了算法運行時間的增速
1.4.2 從算法角度看大 O 表示法：
- 算法運行時間用大 O 表示法表示。
- 算法運行時間并不以秒為單位。
- 算法運行時間是從其增速的角度度量的。
1.4.3 大 O 表示法指出了最糟糕情況下的運行時間
假設要使用簡單查找算法在電話簿中找人，而簡單查找的運行時間為 O(n)，這意味著在最糟糕的情況下，必須查看電話簿中的每個條目。如果要查找的是 Adit ——電話簿中的第一人，一次就能找到，無需查看每個條目。這種情況下這中算法的運行時間依然是 O(n)，因為大 O 表示法不是用來表示最佳情形的，而是最糟糕情形。
1.4.4 一些常見的大 O 運行時間
- O(log n)，也叫對數(shù)時間（如：二分查找）。
- O(n)，也叫線性時間（如：簡單查找）。
- O(n * log n)。
- O(n平方) 。
- O(n!)，著名的商旅問題使用的算法其運行時間就是這個。
