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

Question

我想知道这两种方法的时间复杂度如何比较。我写了第一个 findEmpty 函数，一个朋友写了第二个。两者或多或少都达到了同样的目的，但是，我不确定哪个计算速度更快（如果有的话），为什么？

这些示例来自我们一直在研究的哈希表 class 的实现。此函数在给定参数和 returns 之后找到数组中的下一个空位置。数据作为包含键和值的 Pair 对象存储在数组“arr”中。

我相信这会运行在 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，应将其从所有函数中清除，以使其更易于阅读和理解。请从一开始就写出简洁明了的代码。

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

Direct Recursion vs While Loop for time complexity performance

java

recursion

time-complexity

while-loop