1. 复杂度和简单排序

Tags: 排序算法, 异或, 位运算, 二分法

时间复杂度

• 估计常数操作¹的时间花销的指标，我们叫做 big O，表示为 $O(\cdot )$
• 若算法的时间复杂度和输入有关，则按照最差情况估计（如插入排序）
• 如果两个算法的时间复杂度相同，还需要比较优劣则需要实际去跑来比较具体的时间消耗

选择排序

• 该算法的时间复杂度为 $O(N^2)$，空间复杂度为$O(1)$

  其时间复杂度计算为一个等比数列求和，请自行尝试求解

• 伪代码：

  	Input: arr (arr.shape = [1, N])
  	for i in range(0, N): # -> 重复N次
  		minNum = min(arr[i:N-1])# 找到i位置到最后的最小值 -> 每个看一眼并比较,约2N
  		swap(arr[i], minNum)    # 移动到最前 -> 交换两个数 1

• 实际代码（Java）

冒泡排序

• 操作：相邻位依次比较，大的交换到右边。
• 时间复杂度$O(N^2)$
• 伪代码

  	for i in range(0,N):
  		for j in range(0, N-i):
  			if arr[j] > arr[j+1]:
  				swap(arr[j], arr[j+1])

• 实际代码

插入排序（重要）

• 时间复杂度$O(N^2)$，空间复杂度$O(1)$

  插入排序的时间复杂度收到输入数组的影响，有可能只看一次就完成了排序，也有可能
  需要每一位都从头看到尾

• 步骤：逐步保证0i位置上有序，从i开始，逐步和前面比较，小于前一位即交换，在跟前前一位比较；保证0i位置上有序后，i++，重复上述过程。

• 伪代码：

  for i in range(0,N): 
  	if i == 0: continue # 0不用比，从左往右看
  	for j in range(i, 1):
  		if arr[j]<arr[j-1]: swap(arr[j], arr[j-1])
  		else: break #左侧不小了，跳出

• 真实代码

二分法（重要）

1. 能不能使用二分法和数组有序无序没有关系
2. 最重要的是如何确定二分后选取区间的原则
3. 当问题尝试二分后确定可以甩掉一边，则必定可以二分

1. 在一个有序数组中，找某个数是否存在
   • 如果从左到右遍历，时间复杂度为$O(N)$
   • 二分的方法是最快的，为$O(logN)$
2. 在一个有序数组中，找>=某个数最左侧的位置的数
   • 跟问题1的区别是这个一定是二分到结束，此时区间（二分到结束，也就意味着区间长度为1）最左侧的索引是我们要的.
3. 局部最小值问题
   • 问题 给定无序数组，相邻的两个数一定不相等，返回任一一个局部最小值
   • 思路 若区间的两个端点的单调性相反，则区间内一定存在局部最小。依此来决定每次二分后选取哪个区间继续二分。

对数器

概念：比如你有一个想测的方法A，同时也能实现一个不追求时间复杂度，但是很好想的方法B（或者系统自带的）。写一个能够产生满足A和B输入的随机样本产生器，将样本产生器的样本送到A和B中，比较结果或者程序有没有报错。随后可以通过调整样本产生器产生样本序列长度，测试几千万次，若不出错，则A一定是对的。

异或运算和基于异或运算^的交换函数

异或 , 位运算

• 作用：对应位异或，相同为0不同为1
• 异或运算可以理解成无进位相加
• 性质
  1. 0^N=N, N^N=0 （任何数异或0为自己，异或自己为0）
  2. 满足交换律和结合律：a^b=b^a, a^b^c=a^(b^c)
• 特殊用法：交换数字ab的值

  a = a^b // 此时 a=a^b, b=b
  b = a^b // 此时 a=a^b, b=a^b=(a^b)^b=a^(b^b)=a^0=a
  a = a^b // 此时 a=a^b=(a^b)^a = a^a^b=b, b=a 完成交换

若a和b共享同一个内存，则无法完成交换，会得到0

相关题目

To be reviewed

Footnotes

1. 常数操作指的是和数据量（或者矩阵尺寸）无关的操作，比如两个数求和 arr[1]+2. (如果是链表的数据结构，则不是常数操作，因为要从头找到对应的元素，数组就是常数操作。 ↩