时间与空间复杂度

# 数据结构与算法

### 一、算法性能分析

#### 1.时间复杂度

1）定义：用来定性描述算法的运行时间，一般情况用**Big O**来判断，其表示该算法在最差条件下运行所需时间。

**Big O —— 上限，最差情况 ； Big Omega —— 下限；Big theta—— 中间性能，不好不坏，上下界相等。**

2）**性能排序： O(1) < O(logN) < O(N) < O(N^2) < O(N^3) < O(2^N) < O(N!)**

默认数据规模足够大的情况下，当出现含N的多项式时，一般省略常数项系数，考虑更高次数的影响

个人理解：可以看作函数求极限时，函数随着自变量趋于无穷大时，自身的变化趋势。

3）**递归算法的时间复杂度本质：递归次数*每次递归的时间复杂度**

**4）案例——求x的n次方**

```
int function1(int x, int n) {
int result = 1; // 注意 任何数的0次方等于1
for (int i = 0; i < n; i++) {
result = result * x;
}
return result;
} //时间复杂度Big O(n)

int function2(intx, int n){
if(n==0){
return 1;
}
return function2(x,n-1)*x;
} //时间复杂度Big O(n*1)

int function3(int x, int n){
if(n==0)}{
return 1;
}
if(n%2==1){
return function3(x, n / 2) * function3(x, n / 2)*x;
}
return function3(x, n / 2) * function3(x, n / 2);
} //二叉树算法 时间复杂度Big O(n-1)

int function4(int x, int n){
if(n==0)}{
return 1;
}
t = function4(x, n / 2)
if(n%2==1){
return t * t *x;
}
return t * t;
} // 时间复杂度Big O(logn);n(1/2)^m=1
```

#### 2.空间复杂度

1）定义：用来考虑程序运行时占用内存的大小

2）**递归算法的空间复杂度=每次递归的空间复杂度*递归深度**

3）传递函数参数时，考虑其实是拷贝整个数值还是首元素地址，若是拷贝整个数值，其该层空间复杂度是O(N)，反之，则是O(N)。

#### 3.代码内存消耗

1)内存管理：C/C++ 的堆存空间申请和释放完全自己管理；python内存管理是私有堆空间管理的，所有python对象和数据结构都存储在私有堆空间。程序员没有访问堆权限，只有解释器才行。因此，python将内存封装很好，导致python的基本数据类型所用的内存会远大于存放纯数据类型所占内存。

2）C/C++内存管理：固定部分：代码区和数据区；可变部分：栈区和堆区。

##### **3）为什么64位编译器的指针大小是8个字节？**

1个字节占8个比特，那4个字节就是32个比特，可存放数据大小为2^32=4G空间大小。由于安装的64位操作系统的内存大小已超过4G，若指针还是4个字节，就不能寻址全部的内存地址，因此64位编译器使用8个字节指针寻找所有内存地址

##### 4）为什么需要内存对齐？

1.平台原因：不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些特定地址处取某些特定类型的数据，否则会出现硬件异常。为了同一程序可以在多平台运行，需要内存对齐。

2.硬件原因：内存对齐操作后可以大大提升cpu访问内存的速度。

TRANSLATE with

Bing Webmaster Portal