时间戳

首页 > 解决方案 > 这是正确的时间复杂度吗？

performance - 这是正确的时间复杂度吗？

问题描述

我这样做是为了解决其中一个 leetcode 问题，但我不确定我的算法的复杂性是什么。

public String countAndSay(int n) {
        if (n == 1) return "1";
        String pre = countAndSay(n-1);
        char[] prev = pre.toCharArray();
        int len = prev.length;
        if (len == 1 && prev[0] == '1') return "11";
        int idx = 1;
        int rep = 1;
        String res = "";
        while (idx <= len) {
            if (idx == len) {
                res += (Integer.toString(rep) + prev[idx-1]);
                break;
            }
            if (prev[idx-1] == prev[idx]) rep++;
            else {
                res += (Integer.toString(rep) + prev[idx-1]);
                rep = 1;
            }
            idx++;
        }
        return res;
    }

由于递归发生了 n 次并且循环是 O(n)，我觉得它应该是 O(n^2)。那是对的吗？如果不是，你能解释一下为什么吗？

标签： performancetimetime-complexitybig-ocode-complexity

解决方案

以下是一些事实：

  • 该方法在 input 上递归调用自身n-1。
  • 该方法产生的序列称为look-and-say 序列。
  • 结果字符串的长度随着基数 λ 呈指数增长，其中 λ = 1.303577269034... 是康威常数，因此长度为O(λ^n)。
  • 循环是字符串长度的二次方（因为重复的字符串连接），所以我们有O((λ^n)^2) = O((λ^2)^n)for 循环。

因此，我们可以推导出以下递归关系：

T(0) = 1
T(n) = T(n-1) + O((λ^2)^n)

该关系的渐近行为由下式给出

T(n) ∈ Θ((λ^2)^n) = Θ(1.6993^n)

如果您使用 aStringBuilder而不是进行邪恶的重复字符串连接，则可以将其归结为Θ(λ^n)对于此问题也将是渐近最优的。

推荐阅读