c++ - 递归基础转换时间复杂度分析

Question

Given an integer p and a destination base b, return a string representation of p in base b. The string should have the least significant bit at the end

^ 这就是我给自己的问题。

我想出的朴素递归算法(在 C++ 中)如下:

string convertIntToBaseRecursive(int number, int base) {
  // Base case
  if (!number) return "";

  // Adding least significant digit to "the rest" computed recursively
  // Could reverse these operations if we wanted the string backwards.
  return convertToBaseRecursive(number / base, base) + to_string(number % base);
}

虽然该算法非常简单，但我想确保我理解复杂性分解。我的想法如下，我想知道它们是正确的还是错误的，如果它们是错误的，那么知道我偏离轨道的地方会很好!

声明:

• n = logb(p)为返回字符串的长度
• 时间复杂度:O(n^2)
• 空间复杂度:O(n)

推理:

为了将最低有效位保留在字符串的末尾，当它是我们在其他任何事情之前计算的值时，我们要么必须:

1. 递归地计算字符串
2. 每次我们计算一位时保持“移动”数组，这样我们就可以将最近的一位添加到字符串的前面，而不是末尾
3. 把字符串倒着写，在我们返回之前倒过来(效率最高)

我们正在执行上述 C++ 算法中的第一种方法，+ 运算符在每个堆栈帧处创建一个新字符串。初始帧创建并返回一个长度为 n 的字符串，下一帧创建一个长度为 n-1、n-2 的字符串，n-3，依此类推。按照这种趋势(无需证明为什么 1 + 2 + 3 ... + n = O(n^2)，很明显时间复杂度为 O(n^ 2) = O(logb^2(p))。我们也只需要随时在内存中存储 O(n) 的东西。当原始堆栈帧解析时(就在算法完成之前)我们将根据原始字符串获得内存，但在它解析之前它将根据单个字符 (O(1)) + 递归堆栈帧 ( O(n))。我们在每个级别执行此操作，存储 n 数量的单个字符，直到我们完成。因此空间复杂度为 O(n).

当然，此解决方案的更高效版本是

string convertIntToBaseIterative(int number, int base) {
  string retString = "";

  while (number) {
    retString += to_string(number % base);
    number /= base;
  }

  // Only needed if least significant
  reverse(retString.begin(), retString.end());
  return retString;
}

我相信上面的解决方案，其中 n = logb(p) 有:

• 时间复杂度:O(n)
• 空间复杂度:O(n)

这些分析是正确的还是我错了？

Answer 1

注意事项:

考虑到与 @user1952500 的聊天室对话根据我们谈论的内容，我对他的回答进行了一些编辑。以下是他的回答的编辑版本，反射(reflect)了我们讨论的最新内容和我学到的内容:

---

编辑后的答案:

由于返回值必须包含输出，您无法获得比 O(n) 更好的空间复杂度。

假设输出字符串由以下数字依次组成:a_1, a_2, a_3, ..., a_n。在里面递归方法(项目符号 #1)，我们创建一个字符串，如下所示 "a_1"​​+ "a_2"+ .... + "a_n"，其中递归产生 O(n^2) 时间复杂度。在项目符号 #2 中，迭代方法不断插入角色到字符串的前面，如 (((...(a_1) + a_2) + a_3) + ... + a_n)))...) 移动整个字符串在每个字符添加上也会产生 O(n^2) 时间复杂度。关于您的书面迭代方法(项目符号 #3)时间复杂度可以根据 C++ 的版本进行优化(见下面的注释)。

字符串类型对于涉及重复连接的操作不是很有用。在旧版本的 C++ 中，您可以通过预分配大小为 n 的字符串来实现 O(n) 时间复杂度。在 C++11 中 thisanswer 表示某些附加操作可以优化为单个字符的 O(1) 分摊。假设这是真的，写出的迭代版本将具有 O(1) 时间复杂度，无需任何额外工作。

注意:要使用此算法的递归版本获得 O(n) 时间复杂度，我们可以利用分摊的 O(1)字符追加并使用通过引用传递的单个字符串。这将需要递归版本的函数签名重写如下:

void convertToBaseRecursive(int number, int base, string& str)