一、算法简介
1.1 算法是
-
算法是一组完成任务的指令。任何代码片段都可视为算法。 - 通过查电话问题了解算法
1. 问题：按字母排序的电话本（有 n 个电话号码），从中查找出以 k 开头的某个电话。
2. 问题对应的常用算法有：
简单查找，按顺序一个接一个查，最多需要的步骤是n步；
二分查找，每次过滤一半的值，最多需要的步骤是logn。
log 表示为以2为底的对数；
1.2 二分查找法 （查找列表必须为有序列表，默认递增类型）
/**
二分查找（常见逻辑）
@param sourceArray 源有序排列数数组
@param searchingNum 要查找的数
@return 要查找的数所在数组的位置索引，没有则返回-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 表示法让你能够比较操作数，它指出了算法运行时间的增速
1.4.2 从算法角度看大 O 表示法：
- 算法运行时间用大 O 表示法表示。
- 算法运行时间并不以秒为单位。
- 算法运行时间是从其增速的角度度量的。
1.4.3 大 O 表示法指出了最糟糕情况下的运行时间
假设要使用简单查找算法在电话簿中找人，而简单查找的运行时间为 O(n)，这意味着在最糟糕的情况下，必须查看电话簿中的每个条目。如果要查找的是 Adit ——电话簿中的第一人，一次就能找到，无需查看每个条目。这种情况下这中算法的运行时间依然是 O(n)，因为大 O 表示法不是用来表示最佳情形的，而是最糟糕情形。
1.4.4 一些常见的大 O 运行时间
- O(log n)，也叫对数时间（如：二分查找）。
- O(n)，也叫线性时间（如：简单查找）。
- O(n * log n)。
- O(n平方) 。
- O(n!)，著名的商旅问题使用的算法其运行时间就是这个。
