时间复杂度

什么是时间复杂度

完成整个算法的常数操作的次数
选择排序的时间复杂度
N （看+比+更新）+（N-1）（看+比+更）+... + 1*（看+比+更）
忽略低阶项，和常数项

• 主要是体现出和数据量的关系
• 评价数据量趋向于正无穷的时候

什么是空间复杂度

算法时间复杂度排序

O(1) O(log2N) O(N) O(n2) O(n!) (暴力穷举)

二分法

• 往往是用于有序数组中
  每次都不停的拆成两部分，复杂度是log2N ，O(N)每次都砍一半，砍多久能砍完，肯定比O（N）好
• 有序数组中求大于等于2的最左的位置，不停二分到结束，达标最左的位置是要找的
• 一定要求有序么？ 不一定

  二分法的应用：局部最小

  1） [0] < [1]
  2） [n-1]<[n]
  3） [a-1]<[a]<[a+1]
  满足上述三种情况为局部最小
  如果不满足1和2，那必存在拐点
  找中间值m如果无论是上升还是下架，都可以判断有一个区域一定能确认一个局部最小值

优化方式

1. 数据状况是否特殊
2. 问题性质是否特殊
   是否只需要找一个？是否只需要只需要局部

异或运算的性质和扩展

实质是无进位相加， 1001 + 0101 = 1100
满***换律和结合律
0^N = N, N^N = 0;

无变量交换两个元素

a = a^b
b = a^b
a = a^b

例题1

给定数组arr，只有一个数出现奇数次，其他的数出现偶数次
这里把0和所有的数进行亦或，最后留下的就是奇数次的数

例题2

有两个数出现奇数次，其他的数出现偶数次，找到这两个数

    //优秀的代码
    //取一个数最右边的1
    eor = eor & (~eor + 1);

对数器

网上找吧

递归的思路和复杂度