Linux_C开发_第八天_数据结构和算法简介
本文主要内容:数据结构类型,算法,时间复杂度,空间复杂度,内存分段。
程序 = 数据结构 + 算法
数据结构类型
1. 逻辑类型
(1)线性结构(1:1):
顺序表
链表
栈(FILO)
队列(FIFO)
(2)非线性结构:
层次结构(1:N) ---树状结构
网状结构(N:N)---图
2. 存储类型
存储设备内部数据之间的关系
(1)顺序存储
如数组,堆区(malloc)结构体内部字符串
方便查找不方便增删。
(2)链式存储
方便增删不方便查找。
(3)索引存储
如字典,顺序+链式。
(4)散列存储
哈希(hash)算法.
3. 运算
增,删,改,查,排列
算法
1. 时间复杂度
评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
规则:
多项式:保留最高次幂项,砍去系数。
常数:1。
int a = 1;
a = a+1;
//执行次数是2次.
//这个算法的时间复杂度为O(1).
for(int i=0;i<n;i++) {
//时间复杂度为O(1)的算法
...
}
//上面算法循环体中的代码执行了n次,因此时间复杂度为O(n).
//执行次数是线性的.
for(int number=1; number<n; number*=2) {
//时间复杂度为O(1)的算法
...
}
//随着number每次乘以2后,都会越来越接近n,
//当number不小于n时就会退出循环。假设循环的次数为X,
//则由2^x=n得出x=log₂n,因此得出这个算法的时间复杂度为O(logn)。
//执行次数是对数的.
for(int i=0;i<n;i++){
for(int j=0;j<n;i++){
//复杂度为O(1)的算法
...
}
}
//内层循环的时间复杂度已经得知是O(n),现在经过外层循环n次,
//那么这段算法的时间复杂度则为O(n²)。
//执行次数是一个多项式.
for(int i=0; i<n; i++){
for(int j=0; j<i; j++){
//复杂度为O(1)的算法
}
}
//内循环中int j=0,j<i。
//当i=0时,内循环执行了0次;i=1时内循环执行1次,
//当i=n-1时执行了n-1次,我们可以推算出总的执行次数为:
//n+(n-1)+(n-2)+(n-3)+……+1
//=(n+1)+[(n-1)+2]+[(n-2)+3]+[(n-3)+4]+……
//=(n+1)+(n+1)+(n+1)+(n+1)+……
//=(n+1)n/2
//=n(n+1)/2
//=n²/2+n/2
//只保留最高阶,因此保留 n²/2 再砍去系数
//那么这段算法的时间复杂度则为O(n²)。
常见:
冒泡:n^2
快排:平均 nlog2^n;最大 n^2
2. 空间复杂度
评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。即最大一次使用的空间的大小。
内存分段
--- 内核空间
---
3G----应用层(用户空间)----
--- 主程序传参&环境(argv[])
---
--- 栈区(函数局部变量)
---
--- 垃圾空间
---
--- 堆区(malloc申请)
---
--- 静态区
数据区:
.bss :未初始化的数据
.data:初始化的数据(全局变量,static)
.rodata:只读数据段:字符串常量
--- 只读区
text 代码段
堆区:300M
malloc申请,free释放
不释放容易导致内存泄漏!
函数传参:
全局变量:
以全局变量为耻,以局部变量为荣。
不好维护,空间不影响大量申请。
局部变量:
无static修饰的,存在栈区,函数退出,空间释放。
主函数的局部变量:
不能大量申请,容易导致栈溢出。