数据结构第一章

• 数据的逻辑结构
• 数据的存储(物理)结构
• 时间复杂度
• 空间复杂度

分为线性结构和非线性结构，线性表是典型的线性结构，集合，树与图属于非线性结构。

顺序存储：优点：实现了随机存取；缺点：产生了外部碎片。
（所谓的随机存取是指存取数据所花的时间和数据所在的位置无关）
链式存储：优点：不会出现碎片现象；缺点：每个元素因存储指针占用额外存储空间，只能实现顺序存取

算法中基本运算（最深层循环内的语句）的频度。
例如： f ( n ) = a n 3 + b n 2 + c n f(n)=an^{3}+bn^{2}+cn f(n)=an3+bn2+cn
的时间复杂度为O(n^3);
常见时间复杂度大小为 O ( 1 ) < O ( l o g 2 n ) < O ( n ) < O ( n 2 ) < O ( n 3 ) < O ( 2 n ) < O ( n ! ) < O ( n n ) O(1) 空间复杂度

它是问题规模n的函数，只需分析除输入和程序之外的额外空间。
算法原地工作指算法所需辅助空间为常量，即O(1)。
有时函数递归调用也会带来存储开销。

void C(int n){
	int a,b,c;
	if (n>1){
	C(n-1)
	}
	printf("第%d次/n"，n);
}
void main(){
C(5);
}

这里每调用一次都要创建一个新的abc变量，故空间复杂度为O(n);