如何衡量一个算法的好坏

1.时间复杂度：比较重要

2.空间复杂度 ：现在几乎不关注空间复杂度了，因为内存越来越便宜了。

有的题对时间复杂度有要求！

时间复杂度并不是这个程序执行的时间：程序执行的时间与电脑的好坏有关，时间复杂度算的是执行的次数

时间复杂度是一个函数 下面是他的表示方法

空间复杂度：空间复杂度并不是程序所占内存，而是需要额外创建变量的个数

几道判断时间，空间复杂度的题

上面这道题运算了n*n+2*n+10 次，时间复杂度是n方 （抓大头）

上面这道题时间复杂度是O（n）

上面时间复杂度为O(M+N)

看时间复杂度 不能光看几层循环，要看它的思想

如冒泡排序

for(i=0;i<n-1;i++){

for(j=0;j<n-1-I;j++){

}

}

其思想是走n-1趟，每趟把最大的放在最后面

每趟走n-1-i次

就是等差数列 n-1 n-2 n-3.......1

求和（n-1)*n/2

时间复杂度为O((n-1)*n/2)

即O（n方）

二分查找的时间复杂度为O(log2n)

设最坏情况查找x次

2^x=n

x=log2n;

这种时间复杂度非常高效 

查1000个数 需要   log2 1000 约等于10（2的10次方=1024）

查100W个 要 log2 100W 约等于   20

10亿需要 30 次 

可见非常高效

二分查找确实高效，但是有个缺陷就是前提是有序的，为了到达有序需要排序，如果数据比较多，代价很大。不适合

递归算法的时间复杂度

阶乘为 O（n）

斐波那契额为O(2^n)  是个等比数列的和

用循环写的斐波那契数列把它放入数组中去

 时间复杂度为O(n)

空间复杂度为O(n)  因为多创建了 n个数组

如果用循环写求斐波那契数列的第n个，只需创建三个变量即可，这三个变量一直重复赋值

空间复杂度为O(1)

时间复杂度不变；

算法的时间复杂度

n!最慢 其次     2^n       n*n       n        log2 n

对时间复杂度有要求的经典题

如：消失的数字 

面试题 17.04. 消失的数字 - 力扣（LeetCode）

这道题两种方法

1.算出1~n的和直接用等差数列求和公式，然后减去数组和。得到的就是消失的数字

这种方法没有可移植性，做一道题也就是会这一道题而已。没有学会算法思想。

2.利用操作符（注意操作符都是针对二进制数的）

操作符分为

<<   左移操作符

>>  右移操作符

& 按位与   相当于*   全1才1 有0则0

| 按位或  相当于 +    有一个1就为1 全0才0

^ 按位异或  两数相等则为0 不相等则为1

这道题需要运用按位异或^

int x=0；

先按位异或0~n的数

在按位异或所有数组

for(i=0;i<=n;i++)

{

x=x^i;

}

for(i=0;i<n;i++)

{

x=x^arr[i];

}

旋转数组

思路1：暴力求解

第一层for循环控制旋转多少次

第二层for循环来旋转最后一个数

这种做法时间复杂度O（K*N） 空间复杂度为O(1)

不符合要求

思路二： 

创建一个新数组 把最后的数倒序放入新数组的前K项，然后把剩余n-k个放入数组中

时间复杂度