什么是程序性能

程序性能是指运行这个程序需要的内存和时间的多少，我们用时间复杂度和空间复杂度这两个指标来代表

空间复杂度

程序所需的空间主要由以下构成：

1. 指令空间：指编译后的程序指令所需要的存储空间

2. 数据空间：指所有常量和变量值所需要的存储空间，他由两部分组成：

   1. 常量（如0，1）和简单变量所需要的存储空间
   2. 环境栈空间：用来保存暂停的函数和方法在恢复运行时所需要的信息。如函数func调用了func2，那么我们需要保存在func2结束时func继续执行的指令地址

有时候细微的差距也会带来不同

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        for j in range(n):
            if nums[i] == nums[j]:
                continue
            else:
                i += 1
                nums[i] = nums[j]
        return i + 1

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        for j in range(len(nums)):
            if nums[i] == nums[j]:
                continue
            else:
                i += 1
                nums[i] = nums[j]
        return i + 1

这两个例子功能相同，但是第一种写法采用的是另写一个变量n，而第二个是在for循环中使用len(nums)，两者性能便有了差距，后者执行时间32 ms，消耗内存15.6 MB，而前者则是56 ms，15.5 MB

指令空间：

指令空间的数量取决于一下因素：

1. 把程序转换成机器代码的编译器
2. 在编译时的编译器选项
3. 目标计算器：如是否安装了浮点处理硬件

数据空间：一个结构变量的空间大小是每个结构成员所需的大小之和，如一个数组的大小是数组的长度乘以一个数组元素的空间大小

环境栈空间：每当一个函数被调用的时候，下面的数据将被保存在环境栈中：

1. 返回地址
2. 正在调用的函数的所有局部变量的值以及形参的值（仅对递归函数而言）

大O表示法

函数的渐近增长:给定两个函数f(n)和g(n),如果存在个整数N,使得对于所有的n> N, f(n)总是比g(n)大，那么，我们说f(n)的增长渐近快于g(n)。

换句话说，我们在看一个算法的时间复杂度时，只要看最高次项就可以了，低次项和常数、最高次项前面的系数都是无关紧要的，只要n够大，这些对总体所消耗的时间影响不大，如f(n^3+n+5) ---->f(n^3),而这个最高次项一般是看算法循环嵌套最多的地方，如一个for(i = 0;i<n;i++)循环的时间复杂度是n，计算时嵌套的循环等于内外复杂度之积，如上一个for里面再嵌套一个for，则他的复杂度是n^2

常用的时间复杂度

0(logn)，也叫对数时间，这样的算法包括二分查找
O(n)，也叫线性时间，这样的算法包括简单查找。
0(n* logn)，这样的算法包括快速排序
0(n2)，这样的算法包括选择排序
O(n!)，这样的算法包括旅行商问题的解决方案