数据结构与算法（一）
一、逻辑结构和物理结构的区别
1，数据结构——逻辑结构
逻辑结构表述的是数据与数据之间的逻辑关系
（1）集合结构
所有的数据都属于同一个集合，数据元素之间没有先后顺序。
（2）线性结构
数据与数据之间是一对一的关系。凡是符合一对一关系的结构都是线性结构，比如线性表、队列、栈、数组、字符串等。
（3）树形结构
特点：数据元素之间的关系是一对多。凡是符合一对多关系的结构都是树形结构，比如：二叉树、红黑树等。
（4）图形结构
特点：数据关系多对多。凡是存在多对多关系的结构都是图形结构。
2，数据结构——物理结构
上线提到了，逻辑结构描述的是数据与数据之间的逻辑关系，这些数据之间的关系无论多么复杂，最终都还是要存储到内存中的，数据在内存中的结构体现就是物理结构。
（1）顺序存储结构
开辟一段连续的内存，将数据依次存储进去。
（2）链式存储结构
特点：不需要提前开辟一段连续的空间。
二、时间复杂度
我们在设计算法的时候（写业务代码也同样适用），要按如下的要求去检查和优化自己的代码：正确性->健壮性->可读性->时间效率高和存储量低。
首先，要优先保证你的代码能够准确的将业务展现出来，想想看，如果你的代码都不能正确地表达业务，那么代码的可读性再好、性能再高又有什么用呢？
其次，要保证代码具有足够强的容错性，不要动不动就Crash，要能够兼容大部分的异常场景；
然后，在保证正确性和健壮性的基础上，要让你的代码能够容易被别人读懂；
最后，在保证前三者的基础之上，再考虑去做性能上的优化，比如算法层面的时间空间复杂度、UI层面的卡顿优化内存优化等。
那么如何去评判一个算法的时间效率高呢？用的就是时间复杂度。
在这里，我们使用大O表示法来表示时间复杂度，大O表示法有如下规则：
- 用常数1来取代运行时间中的所有常数
- 在修改运行次数函数中，只保留最高阶项
- 如果最高阶存在且不等于1，则去除该项目相乘的常数
常见的时间复杂度术语，由小到大排列：
- 常数阶
- 对数阶
- 线性阶
- nlogn阶
- 平方阶
- 立方阶
- 指数阶
1，常数阶
O(1)
示例如下：
// 1+1+1=3，所有的常数都用1来替代，所以是O(1)
void testSum1(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum1:%d\n",sum); //执行1次
}
// 1+1+1+1+1+1+1=7，所有的常数都用1来替代，所以是O(1)
void testSum2(int n){
int sum = 0; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
sum = (1+n)*n/2; //执行1次
printf("testSum2:%d\n",sum); //执行1次
}
// O(1)
void add(int x){
x = x+1; // 执行1次
}2，对数阶
O(logn)
void testA(int n){
int count = 1;
while (count < n) {
count = count * 2;
}
}看上面这个例子，如果执行1次，那么 count * 2 = n；
如果执行2次，那么 count * 2^2 = n；
如果执行3次，那么 count * 2^3 = n；
……
如果执行x次，那么 count * 2^x = n；
那么x = log2n，常数均替换为1，那么x = logn
所以时间复杂度是O(logn)
3，线性阶
O(n)
示例如下：
// x=x+1; 这行代码执行n次，O(n)
void add2(int x,int n){
for (int i = 0; i < n; i++) {
x = x+1;
}
}
// 一共执行1+(n+1)+n+1 = 3+2n 次，将所有常数替换为1，因此是 O(n)
void testSum3(int n){
int i,sum = 0; //执行1次
for (i = 1; i <= n; i++) { //执行n+1次
sum += i; //执行n次
}
printf("testSum3:%d\n",sum); //执行1次
}4，nlogn阶
后面会在实例中介绍，这里不做介绍。
5，平方阶
O(n^2)
示例如下：
//x=x+1; 这行代码执行了n*n次，所以时间复杂度是O(n^2)
void add3(int x,int n){
for (int i = 0; i< n; i++) {
for (int j = 0; j < n ; j++) {
x=x+1;
}
}
}再看一个例子：
void testSum4(int n){
int sum = 0;
for(int i = 0; i < n;i++)
for (int j = i; j < n; j++) {
sum += j;
}
printf("textSum4:%d",sum);
}当i=0时，sum += j;这句代码执行n次；
当i=1时，sum += j;这句代码执行n-1次；
当i=2时，sum += j;这句代码执行n-2次；
……
当i=n-1时，sum += j;这句代码执行1次；
所以一共执行n+(n-1)+(n-2)+…+1=(1+n)*n/2=(n^2+n)/2
所有常数项替换为1，并且只保留最高阶项，所以时间复杂度是O(n^2)
再看下面这个例子：
void testSum5(int n){
int i,j,x=0,sum = 0;
for (i = 1; i <= n; i++) {
for (j = 1; j <= n; j++) {
x++;
sum = sum + x;
}
}
printf("testSum5:%d\n",sum);
}可以将下面这两行代码看成是一个整体代码块，那么这个整体代码块一共执行了n*n次，因此时间复杂度是O(n^2)
6，立方阶
O(n^3)
示例如下：
void testB(int n){
int sum = 1; //执行1次
for (int i = 0; i < n; i++) { //执行n次
for (int j = 0 ; j < n; j++) { //执行n*n次
for (int k = 0; k < n; k++) {//执行n*n*n次
sum = sum * 2; //执行n*n*n次
}
}
}
}7，指数阶
O(2^n)或者O(n!)
指数级的时间复杂度在实际项目中是很少预见的，如果一个人能写出指数级时间复杂度的代码，那么这个人也真是神人了。对于指数阶，除非是n特别小，否则将会造成噩梦般的时间消耗，所以我们一般是不会考虑指数级时间复杂度的代码的。
三、空间复杂度
空间复杂度指的是，算法在执行过程中所需的辅助空间。
看下面这个例子：
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(1)
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[i];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}上例中是将数组a[10]给倒序，过程中只使用到了一个临时变量temp，也就是说辅助空间只有1个，因此空间复杂度是O(1)。
还是给数组倒序，我接下来换一种算法实现：
int n = 5;
int a[10] = {1,2,3,4,5,6,7,8,9,10};
//算法实现(2)
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}在这种算法中，数组b就是辅助空间，一共为数组b开辟了n个元素，因此使用到了n个辅助空间，所以空间复杂度是O(n)。
另外需要说明的一点是，我们在衡量一个算法的时候，是要根据该算法可能出现的最差的情况去衡量。
以上。
腾讯云开发者
