前面几节课的内容都比较简单, 而且以前我也学习过一些, 所以不是特别重要的我不会写的太详细。
🍕 认识时间复杂度
时间复杂度, 一般指的是最坏的情况下运行的时间, 用 O() 表示。
当时间复杂度相同时, 再次比较性能, 一般是实践来计算时间, 而不是比较那些常数项。 因为一次操作, 在数学上表示出来都是 1, 但实际运行时间并不一定相等。 比如一次乘法和一次位运算, 虽然都是一次操作, 但他们的运行时间是不一样的。
了解内容: 评估最好情况时间复杂度用 Θ（大 theta）符号; 评估平均情况时间复杂度用 Ω（大 omega）符号;
【注意⚠️】: 时间复杂度只能算是最低标准, 我们需要优化的, 基本是常数时间。 时间复杂度是数学家的事情, 是搞理论的人研究的。 实践中要优化的是常数时间。
🍕 选择排序
核心思路: 每次遍历, 都取出最小的数。
比如一个数组 [0, ... ,N-1]
第一遍遍历 0 ~ N-1, 找到最小值, 放到 0 位置上
第二遍遍历 1 ~ N-1, 找到最小值, 放到 1 位置上
第三遍遍历 2 ~ N-1, 找到最小值, 放到 2 位置上
第四遍遍历 3 ~ N-1, 找到最小值, 放到 3 位置上
...以选择排序为例, 介绍时间复杂度
下面每一个双引号引起来的内容, 都算是一次常数时间。
第一遍遍历, 每个数都得"看一眼", 所以看了 N 眼
看到的每一个数, 都需要和前面找到的最小值进行"比较", 所以需要比较 N-1 次, 约等于比较了 N 次
看完了, 比较完了, 找到最小的数后, 将这个数与第 0 位置上的数"交换"
第二遍遍历, 同样每个数都要"看一眼", 所以看了 N-1 眼, 因为第 0 位置上的数已经排序好了
同理, "比较"也大概比较了 N-1 次
"交换" 也只交换一次。
...
...
...
以此类推, 当排序完成后, 一共看了 N + (N-1) + (N-2) + ... + 1 眼
一共比较了 N + (N-1) + (N-2) + ... + 1 次
一共交换了 1 + 1 + ... + 1 = N 次
总共执行的操作大概是 a*N^2 + b*N + c,
其中 a,b,c 是常数, 忽略常数, 忽略低阶, 最终得到时间复杂度 O(N^2)🍕 冒泡排序
核心思路: 每次冒泡, 都将最大的数冒泡上去, 即每次遍历, 都将最大的数放到了最后面
🍕 异或运算
异或(Exclusive OR, xor), 用符号 ^ 或者 ⊕ 表示, 规定如下:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0可以看出, 异或运算相当于 "无进位相加"。
根据上面规定, 可以得出异或有以下性质:
0 ^ N = N; 0 异或任何数 N 都等于 NN ^ N = 0; 两个相同的数字异或结果是 0, 这叫做"自反性"a ^ b = b ^ a; 满足交换律a ^ (b ^ c) = (a ^ b) ^ c满足结合律- 满足对偶性, 即 (a ⊕ b) ⊕ b = a 或者 (a ⊕ b) ⊕ a = b
根据以上内容, 可以知道多个数执行异或操作时, 顺序不重要, 并且可以根据异或来处理有关奇偶性的问题。
异或案例 1 - 交换
在程序中, 对于拥有独立空间的两个变量, 可以通过异或操作来交换两个变量的值
a = a ^ b
b = a ^ b
a = a ^ b证明
假设 a = 甲, b = 乙
a = a ^ b 结果: a = 甲 ^ 乙, b = 乙
b = a ^ b 结果: a = 甲 ^ 乙, b = 甲 ^ 乙 ^ 乙 = 甲
a = a ^ b 结果: a = 甲 ^ 乙 ^ 甲 = 乙, b = 甲
故最终 a = 乙, b = 甲这种方式很取巧, 还不建议用, 因为有漏洞, 当两个数的位置相同时, 两个数都会被变成 0, 比如下面例子
a = [1,2,3]
def swap(i, j):
a[i] = a[i] ^ a[j]
a[j] = a[i] ^ a[j]
a[i] = a[i] ^ a[j]
swap(0, 0)
print(a) # [0, 2, 3]异或案例 2 - 求出现奇数次的数
对于一个数组, 已知其中只有一个数出现奇数次, 其他数都出现偶数次, 请求出这个奇数次的数, 要求空间复杂度 O(1), 时间复杂度不大于 O(n)
思路: 定义一个变量 eor, 然后遍历数组, 每次都将数组内的元素与 eor 进行异或操作, 最后的结果就是只出现奇数次的数。
原理很简单, a ^ b ^ c ... ^ d, 假设其中 a, b, c 都出现了偶数次, 那么他们的异或结果就是 0, 假设 d 出现了奇数次, 那么他们异或的结果就是 d。
异或案例 3 - 求出现奇数次的两个数
这是案例 2 的进阶版。 对于一个数组, 已知其中只有两个数出现奇数次, 其他数都出现偶数次, 请求出这两个奇数次的数, 要求空间复杂度 O(1), 时间复杂度不大于 O(n)
方法是差不多的, 假设这两个数是 a 和 b, 很明显遍历完后的 eor = a ^ b
然后求出二进制形式下 eor 中最右侧为 1 的位置。
为什么要求这个位置呢? 因为这个位置可以区分出 a 和 b
由题意易得, a 和 b 是不相等的, 并且 eor = a ^ b, 两个不相等的数进行异或操作, 其中二进制形式下, 值为 1 的结果肯定是一个 0 一个 1 进行异或得到的。 所以可以根据这一位来区分出 a 和 b。
然后再次遍历数组, 根据某一位是否为 1, 可以将数组的数字划分两类, 并且我们能够保证 a 和 b 处于不同类。 这个时候, 这个问题就被简化成案例 1 了, 我们只需要再遍历一次, 就可以求出 a 或者 b 了。
伪代码如下：
eor = 0
for item in arr:
eor ^= item
# 此时的 eor = a ^ b
# 因为 a != b, 所以二进制 eor 必定有一个位置为 1
right_one = eor & (~eor + 1) # 这种方式能够取出最右侧的 1
a = 0
for item in arr:
if (item & right_one) == 0:
a ^= item
b = a ^ eor
a, b🍕 插入排序
核心思路: 就像玩扑克一样, 先排序好一个, 然后排序好两个, 以此类推, 直到全部排好序
具体描述:
首先, 0 ~ 0 是不用排序的, 因为就一个
第一遍, 取出位置 1 的数, 将它插入到 0 ~ 1
第二遍, 取出位置 2 的数, 将它插入到 0 ~ 2
第三遍, 取出位置 3 的数, 将它插入到 0 ~ 3
...
假设是从小到大排序:
插入的过程是, 将这个数依次与前面的数比较, 如果这个数小于前面的数, 则交换两个位置, 直到这个数大于前面的数或者遇到边界🍕 二分法
基本思路: 每次都排除一半
时间复杂度: log2(N), 一般都是以 2 为底, 所以 log(N) 没有明确指定底数时, 默认底数都是 2。
理解时间复杂度是 log(N):
比如数组长度为 8, 则每次查找的长度为:
8 4 2 1
又比如长度是 16, 则每次查找的长度为:
16, 8 ,4, 2, 1
每次都是砍一半, 所以是以 2 为底的 log(N)二分法案例 1 - 有序查找某数的位置
已知一个数组是有序的, 现在要查找 a, 则可以使用二分查找
基本步骤:
先取中间的一个数 x, 然后比较 x 是否等于 a
如果等于则直接返回
如果 x 大于 a 则继续查找 x 的左侧, 在左侧继续使用二分查找
如果 x 小于 a 则继续查找 x 的右侧, 在右侧继续使用二分查找二分案例 2 - 有序查找某数最左侧的位置
题意和案例 1 差不多, 只不过当有多个符合的值时, 要求最左侧的值
步骤和前面差不多, 只不过前面查找到等于时就直接返回了, 而这里是会继续二分下去, 直到结束。 需要注意的是, 因为这里求的是最左侧, 所以遇到偶数长度时, 中点是偏向左边的。 同理, 如果是要找右侧的, 则中点是偏向右侧的。
定义一个变量 t
步骤和前面一样, 只不过遇到 x 等于 a 时, 更新t
二分结束后的 t 就是最左侧的值二分案例 3 - 局部最小值问题
二分法不仅仅适用于有序的。
题意: 数组是无序的, 但保证相邻两个数之间数值一定不同, 求任意一个局部最小值。
局部最小值： 假设一个数 a 若 a 位于最右侧, 并且 a 小于左旁的数, 则 a 是局部最小值; 如 a 位于最左侧, 并且 a 小于右旁的数, 则 a 是局部最小值; 若 a 位于中间, 并且 a 小于两旁的数, 则 a 是局部最小值。
步骤和前面差不多:
判断最左侧的数是否满足局部最小值, 如果满足则直接返回
判断最右侧的数是否满足局部最小值, 如果满足则直接返回
否则, 步骤和前面一样, 二分法查找, 只不过这次的条件是
若 a 小于两旁的数, 则直接返回
若 a 大于两旁的数, 则任选一旁继续二分
若 a 大于右侧, 小于左侧, 则往右侧继续二分
若 a 大于左侧, 小于右侧, 则往左侧继续二分依据: 若最左和最右的数都不是局部最小值, 则中间一定存在局部最小值, 因为相邻两个数不相等。
-
- /
\ /
\ /
\ 中间一定存在局部最小值🍕 对数器
不是所有算法都可以通过线上 og 来判断正确还是错误, 比如排序算法。 而且线上 og 中给出的测试用例也是人给的, 也可能出现误判对的情况。 这个时候就可以利用对数器。
对数器可以用来测试算法的正确性。
对数器会生成一些随机的输入数据, 然后将待测试的算法和另一个可靠的算法进行比较, 以确保算法的正确性。
🍕 伪代码
选择排序
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) { // i ~ N-2
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) { // i+1 ~ N-1
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}冒泡排序
if (arr == null || arr.length < 2) {
return;
}
for (int e = arr.length - 1; e > 0; e--) { // N-1 ~ 1
for (int i = 0; i < e; i++) { // 0 ~ e-1
if (arr[i] > arr[i+1]) {
swap(arr, i, i+1)
}
}
}插入排序
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) { // 1 ~ N-1
for (int j = i-1; j >=0 && arr[j] > arr[j+1]; j--) { // i ~ 0
swap(arr, j, j+1);
}
}