algs4-1.4.11: 这次 GPT4 算错了时间复杂度
1.4.11 为StaticSETofInts添加一个实列方法 howMany() (请见表1.2.15),找出给定键的出现次数且在最坏情况下所需的运行时间应该和logN成正比。
我的解题思路
- 首先是找到 表1.2.15 (P61~P62), 把对应代码敲下来:
package algs4;
import java.util.Arrays;
import edu.princeton.cs.algs4.StdOut;
public class StaticSETofInts {
private int[] a;
public StaticSETofInts(int[] keys) {
a = new int[keys.length];
for (int i = 0; i < keys.length; i++) {
a[i] = keys[i]; // 保护性复制.
}
Arrays.sort(a);
}
public boolean contains(int key) {
return rank(key) != -1;
}
private int rank(int key) {
// 二分查找.
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// 键要么存在于 a[lo..hi] 中, 要么不存在.
int mid = lo + (hi - lo) / 2;
if (key < a[mid])
hi = mid - 1;
else if (key > a[mid])
lo = mid + 1;
else
return mid;
}
return -1;
}
}
- 设计一个简易够用的测试用例:
public static void main(String[] args) {
int key = 2;
int[] a = { key, key };
int[] b = { key, key, key };
int[] c = { key, key, key, key };
int[] d = { key, key, key, key, key };
StaticSETofInts objA = new StaticSETofInts(a);
StaticSETofInts objB = new StaticSETofInts(b);
StaticSETofInts objC = new StaticSETofInts(c);
StaticSETofInts objD = new StaticSETofInts(d);
StdOut.println("key=" + key + "\t" + Arrays.toString(a) + "\t\t\thowMany = " + objA.howMany(key));
StdOut.println("key=" + key + "\t" + Arrays.toString(b) + "\t\thowMany = " + objB.howMany(key));
StdOut.println("key=" + key + "\t" + Arrays.toString(c) + "\t\thowMany = " + objC.howMany(key));
StdOut.println("key=" + key + "\t" + Arrays.toString(d) + "\t\thowMany = " + objD.howMany(key));
key += 1;
StdOut.println("key=" + key + "\t" + Arrays.toString(a) + "\t\t\thowMany = " + objA.howMany(key));
StdOut.println("key=" + key + "\t" + Arrays.toString(b) + "\t\thowMany = " + objB.howMany(key));
StdOut.println("key=" + key + "\t" + Arrays.toString(c) + "\t\thowMany = " + objC.howMany(key));
StdOut.println("key=" + key + "\t" + Arrays.toString(d) + "\t\thowMany = " + objD.howMany(key));
}
-
实现 howMany() 方法: 因为有1.4.10作为基础,所以思路也很容易想到. 我当时在检索 1.4.11 的解法时, 有些题解也提前泄露了 1.4.11 可能的思路.
-
直接计算key的最大和最小索引, 然后相减即可.
-
因为本质上是进行了常数次二分查找, 所以时间复杂度还是 O(logN).
private int rankMin(int key) { // 二分查找. int lo = 0; int hi = a.length - 1; while (lo <= hi) { // 键要么存在于 a[lo..hi] 中, 要么不存在. int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else if (mid - 1 >= 0 && a[mid - 1] == key) hi = mid - 1; else return mid; } return -1; } private int rankMax(int key) { // 二分查找. int lo = 0; int hi = a.length - 1; while (lo <= hi) { // 键要么存在于 a[lo..hi] 中, 要么不存在. int mid = lo + (hi - lo) / 2; if (key < a[mid]) hi = mid - 1; else if (key > a[mid]) lo = mid + 1; else if (mid + 1 < a.length && a[mid + 1] == key) lo = mid + 1; else return mid; } return -1; } // for 1.4.11 public int howMany(int key) { int min = rankMin(key); if (-1 == min) return 0; return 1 + rankMax(key) - rankMin(key); }- 用例代码输出如下:
key=2 [2, 2] howMany = 2 key=2 [2, 2, 2] howMany = 3 key=2 [2, 2, 2, 2] howMany = 4 key=2 [2, 2, 2, 2, 2] howMany = 5 key=3 [2, 2] howMany = 0 key=3 [2, 2, 2] howMany = 0 key=3 [2, 2, 2, 2] howMany = 0 key=3 [2, 2, 2, 2, 2] howMany = 0 -
看看 GPT4 有何高见!
- 首先, 它用自己的话重复了以下我的问题:
在已有的 StaticSETofInts 类中添加一个新的实例方法 howMany() 可以使用二分查找的原理来实现，具体可以通过找到数组中最左边和最右边与目标数值相等的元素，然后计算这两个元素之间的数量，其中最坏情况的运行时间和 logN 成正比。
所以, 我可以认为它是已经 “理解” 了我的问题的.
- 但是它给出的答案, 明显是不符合题意的.它的答案, 最坏情况下, 明显是 O(N) 的. 因为它打算往左右遍历所有的和key相同的元素, 然后基于遍历来计数:
public int howMany(int key) {
// 如果数组不含该元素,直接返回0
if (!contains(key)) {
return 0;
}
int i = rank(key);
int count = 1;
// 向左查找
for (int j = i-1; j >= 0 && a[j] == key; j--) {
count++;
}
// 向右查找
for (int j = i+1; j < a.length && a[j] == key; j++) {
count++;
}
return count;
}
- 当然, 在我最终让它重新检查下算法的时间复杂度后, 给出了符合要求的答案. 虽然和我的答案不完全一样. 但是本质上是没有差别的.
小感: 机器学习时代, 人人都应该学习点机器学习的 基本知识.
如果对机器学习完全不了解的话, 可能会很困惑: 它明明已经 “理解” 了我的问题, 它甚至还重复了一遍关键点.
基于我有限的了解, 机器学习模型, 有好多 weight 值, 有点类似于网页的 Page Rank 排名. 当你在搜索引擎中,输入不同的关键词组合, 得到的组合不一样. 是因为 搜索引擎 综合考虑了网页的 PR 和你关键词之间的关联性, 然后给出它认为可能正确答案. 嗯…这个类比,其实不是非常恰当. 但是勉强可以辅助理解. 简单说就是: 虽然是同一个模型, 当我们输入不同的提示词组合, 模型内部处理问题的侧重点, 其实是不一样的.这就导致, 我们可能要适当变换提示词, 或者基于上下文进一步引导, 才能得到符合我们需要的答案.
附图: GPT4 完整聊天记录.
