直接递归与While循环的时间复杂性性能

Question

我想知道这两种方法的时间复杂性比较如何。我写了第一个findEmpty函数，一个朋友写了第二个。然而，两者或多或少都实现了相同的目标，我不确定哪一个计算得更快(如果有的话(，为什么？

这些例子来自我们一直在研究的一个hashtable类的实现。这个函数在给定参数之后找到数组中的下一个空位置并返回它；arr"；作为包含键和值的Pair对象。

我相信这将运行在O(1(：

private int findEmpty(int startPos, int stepNum, String key) {
if (arr[startPos] == null || ((Pair) arr[startPos]).key.equals(key)) {
return startPos;
} else {
return findEmpty(getNextLocation(startPos), stepNum++, key);
}
}

我相信这将运行在O(n(：

private int findEmpty(int startPos, int stepNum, String key) {  
while (arr[startPos] != null) {
if (((Pair) arr[startPos]).key.equals(key)) {
return startPos;
}
startPos = getNextLocation(startPos);
}
return startPos;
}

这是Pair对象和getNextLocation:的代码

private class Pair {
private String key;
private V value;
public Pair(String key, V value) {
this.key = key;
this.value = value;
}
}
private int getNextLocation(int startPos) {
int step = startPos;
step++;
return step % arr.length;
}

我想我的理解是错误的，可能还没有尽可能简洁地处理这个问题，但我很感激并欢迎任何更正。

Answer 1

您的解决方案与您朋友的解决方案具有相同的时间复杂性。两者都与数组的长度成线性关系。递归并没有将时间复杂度降低到O(1(，因为它一直调用getNextLocation，直到找到密钥。

在您的功能中，getNextLocation

private int getNextLocation(int startPos, int stepNum) {
int step = startPos;
step++;
return step % arr.length;
}

第二个参数stepNum从未在这个函数中使用过，应该从所有函数中清除它，以便于阅读和理解。请从头开始写简洁明了的代码。