基本概念：
算法（Algorithm）：⼀个计算过程，解决问题的⽅法
Niklaus Wirth: “程序=数据结构+算法”
时间复杂度
时间复杂度：⽤来评估算法运⾏效率的⼀个式⼦
经验
当算法过程出现循环折半的时候， 复杂度式⼦中会出现logn.
时间复杂度是⽤来估计算法运⾏时间的⼀个式⼦（单位）
常⻅的时间复杂度（按效率排序） O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n2logn)<O(n3)
复杂问题的时间复杂度 O(n!) O(2n) O(nn)
如何简单快速地判断算法复杂度
快速判断算法复杂度（适⽤于绝⼤多数简单情况）
确定问题规模n
循环减半过程→logn
k层关于n的循环→n^k
空间复杂度
空间复杂度：⽤来评估算法内存占⽤⼤⼩的式⼦
空间复杂度的表示⽅式与时间复杂度完全⼀样
算法使⽤了⼏个变量：O(1)
算法使⽤了⻓度为n的⼀维列表：O(n)
算法使⽤了m⾏n列的⼆维列表：O(mn)
查找
查找：在⼀些数据元素中，通过⼀定的⽅法找出与给定关键字相同的数据 元素的过程。
列表查找（线性表查找）：从列表中查找指定元素
输⼊：列表、待查找元素
输出：元素下标（未找到元素时⼀般返回None或-1）
顺序查找 (Linear Search)
顺序查找：也叫线性查找，从列表第⼀个元素开始，顺序进 ⾏搜索，直到找到元素或搜索到列表最后⼀个元素为⽌。
时间复杂度：O(n)
代码
#include "stdio.h"
int FindNumber(int pInt[6], int n, int key);
//顺序查找
int main(){
//定义一个数组
int arr[] = {4, 5, 6, 8, 11, 1};
//n为长度
int n = sizeof (arr) / sizeof (arr[0]);
int key;
printf("Input what you want to look for:\n");
scanf("%d", &key);
int result = FindNumber(arr, n, key);
if(result != 0){
printf("found,position is %d", (result + 1));
} else{
printf("not found!");
}
return 0;
}
//逐个比较
int FindNumber(int arr[6], int n, int key){
int i = 0;
for(i = 0; i < n; i++){
if(arr[i] == key){
return i;
}
}
return 0;
}二分查找：
⼆分查找：⼜叫折半查找，从有序列表的初始候选区中间开
始，通过对待查找的值与候选区中间值的⽐较，可以使候选
区减少⼀半
#include "stdio.h"
int bin_search(int arr[], int length, int key){
int low = 0, high = length;
while (low <= high){
int mid = (low + high) / 2;
if(arr[mid] == key){
printf("found!");
return mid;
} else if(arr[mid] < key){
//大了往右
low = mid + 1;
} else{
//小了往左
high = mid - 1;
}
}
return -1;
}
int main(){
int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
int length = sizeof (arr) / sizeof (arr[0]);
int key, res;
printf("input the key_number:\n");
scanf("%d", &key);
res = bin_search(arr, length, key);
if(res == -1){
printf("not found");
} else{
printf(" the %d is found", key);
}
return 0;
}
