README
# README
# 概念
程序 = 数据结构+ 算法
# 算法复杂度
算法的复杂性体现在运行该算法时计算机所需要的资源多少上 ,计算机资源最重要的是时间和空间(寄存器)资源,因此复杂度分为时间和空间复杂度
# 时间复杂度
是指执行算法所需要的计算工作量,指时间增长的趋势。T(n) = O( f ( n ) )
- 常用时间复杂度量级:
常数阶O(1): 算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。
int x = 0; int y = 1; int temp = x; x = y ; y = temp;
1
2
3
4
5该程序段的执行时间是一个与问题规模n无关的常数
对数阶
:由于计算机使用二进制的记数系统,对数常常以2为底(即 ,有时写作 )。然而,由对数的换底公式, 和 只有一个常数因子不同,这个因子在大O记法中被丢弃。因此记作 ,而不论对数的底是多少,是对数时间算法的标准记法。 典型的二分查找法:假如有32份试卷,你丢一次,还剩16份 ,丢两次,还剩下8 份,丢三次,就只剩下4份了,可以这么一直丢下去,丢到第五次,就只剩下一份了。而 。也就是我们一次丢一半,总要丢到只有一份的时候才能出结果,如果有n份,那么显然我们就有线性阶O(n): 随着样本数量的增加,复杂度也随之线性增加
for(int i = 1;i<=n;i++){ x++; //O(1+3N)=O(N) }
1
2
3线性对数阶O(nlogN): 比如对一堆带有序号的书进行排序。先选一本,然后把号码大于这本书的扔右边,小于这本书的扔左边。因为每本书都要比较一次,所以这么搞一次的复杂度是 O(n),那么快排需要我们搞多少次呢?这个又回到了二分查找的逻辑了,每次都把书堆一分为二,请问分多少次手里才能只剩下一本书呢?答案还是logn。而从代码的角度来说,在到达大小为一的数列之前,我们也是需要作logn次嵌套的调用。
方阶
: 计算的复杂度随着样本个数的平方数增长 在比如说构建一个网络,每个点都和其他的点相连。显然,每当我们增加一个点,其实就需要构建这个点和所有现存的点的连线,而现存的点的个数是n,所以每增加1,就需要增加n个连接,那么如果我们增加n个点呢,那这个连接的个数自然也就是 量级了。TODO
- 立方阶
- k次方阶
- 指数阶
- 阶乘 O( n!)
- 立方阶
# 空间复杂度
是指对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势。S(n) = O( f ( n ) )
- 常见的空间复杂度
:、 、 O(1) 如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)
int x = 0; int y = 0; x++; y++;
1
2
3
4代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)
O(n)
int[] newArray = new int[n]; for(int i = 0; i < 0; i++){ newArray[i]=i; }
1
2
3
4上面这段代码中,new了一个数组出来,占用空间大小为n,后面的for循环只是给这个数组赋值并没有分配新的空间,因此这段代码的空间复杂度主要取决于 n 的大小。
比如说二维数组...