算法与数据结构
算法：算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表示⼀个或多个操作。
算法设计要求：（正确性，可读性，健壮性，时间效率高，存储量低）
1.数据结构
数据结构：数据----->数据对象----->数据元素----->数据项
2.数据分类
一.逻辑结构划分
(1).集合结构
(2).线性结构
(3).树形结构
(4).图形结构
二.物理结构
(1).顺序存储结构
(2).链式存储结构
3.数据结构和算法关系
image
3.数据结构------常见的时间复杂度（大O表示法）
image
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式：S(n) = n(f(n))其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数
举例
1.常数阶时间复杂度计算O(1)
3 O(1)
void testSum1(int n){
int sum = 0; //执行一次
sum = (1+n)/2; //执行一次
printf("testSum1:%d\n",sum); //执行一次
}
//7次 O(1)
void testSUm2(int n){
int sum = 0;//执行一次
sum = (1+n)*n/2;//执行一次
sum = (1+n)*n/2;//执行一次
sum = (1+n)*n/2;//执行一次
sum = (1+n)*n/2;//执行一次
sum = (1+n)*n/2;//执行一次
printf("testSum2:%d\n",sum); //执行一次
}
//x=x+1; 执行一次 O(1)
void add(int x){
x = x+1;
}
2.线性阶时间复杂度计算O(n)
void add2(int x, int n){
int i, sum = 0; //执行1次
for (i=1; i <=n; i++){ //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}
3.对数阶时间复杂度计算O(logn)
//2的x次方等于n x = log2n -> logn
void testA(int n){
int count = 1; //执行1次
while (count < n){
count = count * 2;
}
}
3.平方阶时间复杂度计算O(n^2)
void add3(int x, int y){
for (int i = 0; i < n; i++){ //执行n次
for(int j = 0; j < n; j++){ //执行n次
x = x +1;
}
}
}
//n+(n-1)+(n-2)+...+1 = n(n-1)/2 = n^2/2+ n/2 = O(n^2)
void add3(int x, int y){
for (int i = 0; i < n; i++){ //执行n次
for(int j = i; j < n; j++){ //执行n次
x = x +1;
}
}
}
