1、算法时间复杂度1.1算法时间复杂度的定义：
进行算法分析时，句子的总执行次数t(n )是关于问题规模n的函数，进而分析n引起的t ) n )的变化，决定t ) n )的顺序。 将所述算法的时间复杂度，即，所述算法的时间度量表示为t(n )=o (n ) )至f(n )。 这表明随着问题规模n的增大，算法运行时间的增长率与f(n )的增长率相同，称为算法的渐近时间复杂度，简称时间复杂度，是一种“渐进表示法”。 这里，f(n )是有问题规模n的函数。
用大写o ()表示算法时间复杂性的符号叫做大o符号。
一般来说，随着输入规模n的增大，t(n )增长最慢的算法将成为最佳算法。
很明显，从该算法的时间复杂度的定义可以看出，我们的3个加法算法的时间复杂度分别为o(1)，o(1 )，o ) ) n^2)。
1.2 )推导大o阶方法分析一种算法的时间复杂度：
将执行时间中的所有加法常数替换为常数1。 修改后的执行次数函数只保留顶层项目。 当存在最高位项且不是1时，去除与该项相乘的常数。 得到的最后结果是很大的o阶。 常数步长
/段码的大o是多少？
int sum=0，n=100； printf(「Iloveyou.comn”)； printf(「Iloveyou.comn”)； printf(「Iloveyou.comn”)； printf(「Iloveyou.comn”)； printf(「Iloveyou.comn”)； printf(「Iloveyou.comn”)； sum=(1n ) ) n/2； 第一条表示所有的加法常数只要给他o(1)就可以了
线性阶：一般含非嵌套环与线性阶相关。 线性次数是指随着问题规模n的增大，对应的计算次数直线增加。
int i，n=100，sum=0； for(I=0； i n； I ) { sum=sum i； }上面的代码需要执行n次循环体的代码，因此循环的时间复杂度为o(n )。
平方步长
int i，j，n=100； for(I=0； i n； I ) for(j=0； j n； j ) (printf )“Ilovefishc.comn”)； }n是100。 这意味着每执行一次外部循环，就会执行100次内部循环。 要使总程序退出这两个循环，必须运行100*100次，这是n的平方。 因此，此代码的时间复杂度为o(n^2)。
总结：如果有三个这样的嵌套循环，那就是n^3。 因此，循环的时间复杂度为循环整体的复杂度乘以该循环被执行的次数。
int i，j，n=100； for(I=0； i n； I ) for(j=I； j n； j ) (printf )“Ilovefishc.comn”)； i=0时，内环执行n次，i=1时，内环执行n-1次。i=n-1时，内环执行1次，因此总的执行次数应该如下。
n(n-1 ) n-2 )…1=n ) n1 )/2
n(n1 )/2=n^2/2 n/2
我们引导大o的攻略，第一条无视。 因为没有常数加法。 第二条只保留最高项，所以去掉n/2。 去除第三条、最高项上的常数，最终得到o(n )2)。
对数阶数
int i=1，n=100； wile(In ) { i=i * 2； }每次在i*2之后，都离n更近了一步，所以当x个2乘以n以上时，就会退出循环。
于是，由于可以从2^x=n中得到x=log(2) n，所以该循环的时间复杂度为o ) O(logn )。
1.3函数调用的时间复杂度分析int i，j； for(I=0； i n； I ) {function(I )； }voidfunction(intcount ) ) printf )“%d”，count )； }函数体是打印这个参数，这个很好理解。 由于function函数的时间复杂度为o(1)，因此整体的时间复杂度为循环的次数o ) n )。
假设函数如下所示：
voidfunction(intcount ) { int j； for(j=count； j n； j ) (printf )“%d”，j )； }实际上，这和之前平方次数时举出的第二个例子相同。 由于函数内部的循环次数随着count的增加(接近n )而减少，所以游戏攻略算法的时间复杂度为o(n^2)。
n； //1函数(n )； //1for(I=0； i n； I ) (/nfunction ) ) I； (for ) I=0； i n； I ()/n ) 2for ) j=I； j n； j ) printf(“%d”，
j); }}void function(int count) { printf(“%d”, count);}为：1+1+n+n2，所以最后是O(n2)
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
我们查找一个有n个随机数字数组中的某个数字，最好的情况是第一个数字就是，那么算法的时间复杂度为O(1)，但也有可能这个数字就在最后一个位置，那么时间复杂度为O(n)。
平均运行时间是期望的运行时间。
最坏运行时间是一种保证。在应用中，这是一种最重要的需求，通常除非特别指定，我们提到的运行时间都是最坏情况的运行时间。
我们在写代码时，完全可以用空间来换去时间。
举个例子说，要判断某年是不是闰年，你可能会花一点心思来写一个算法，每给一个年份，就可以通过这个算法计算得到是否闰年的结果。
另外一种方法是，事先建立一个有2050个元素的数组，然后把所有的年份按下标的数字对应，如果是闰年，则此数组元素的值是1，如果不是元素的值则为0。这样，所谓的判断某一年是否为闰年就变成了查找这个数组某一个元素的值的问题。
第一种方法相比起第二种来说很明显非常节省空间，但每一次查询都需要经过一系列的计算才能知道是否为闰年。第二种方法虽然需要在内存里存储2050个元素的数组，但是每次查询只需要一次索引判断即可。
这就是通过一笔空间上的开销来换取计算时间开销的小技巧。到底哪一种方法好？其实还是要看你用在什么地方。
2.1 算法的空间复杂度定义算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数，也是一种“渐进表示法”，这些所需要的内存空间通常分为“固定空间内存”（包括基本程序代码、常数、变量等）和“变动空间内存”（随程序运行时而改变大小的使用空间）
通常，我们都是用“时间复杂度”来指运行时间的需求，是用“空间复杂度”指空间需求。
当直接要让我们求“复杂度”时，通常指的是时间复杂度。
它的空间复杂度O（n）=O（1）；
def fun(n): k = 10 if n == k: return n else: return fun(++n)递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。
for(i=0;i<n;++): temp = i变量的内存分配发生在定义的时候，因为temp的定义是循环里边，所以是n*O(1)
temp=0;for(i=0;i<n;i++): temp = itemp定义在循环外边，所以是1*O(1)
3. 常用算法的时间复杂度和空间复杂度参考：https://www.jianshu.com/p/88a1c8ed6254
https://blog.csdn.net/halotrriger/article/details/78994122
https://blog.csdn.net/daijin888888/article/details/66970902