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

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)是return字符串的长度
时间复杂度：O(n^2)
Space 复杂度：O(n)

推理：

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

像我们一样递归计算字符串
每次计算一位时都保留"shifting"数组，这样我们就可以将最近的一位添加到字符串的前面，而不是末尾
把字符串倒着写，在我们之前倒过来return（效率最高）

我们正在执行上述 C++ 算法中的第一种方法，+ 运算符在每个堆栈帧处创建一个新字符串。初始帧创建 return 长度为 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 数量的单个字符，直到我们完成。因此 space 复杂度为 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)
Space 复杂度：O(n)

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

Answer 1

由于 return 值必须包含输出，因此无法获得比 O(n).

更好的 space 复杂度

假设输出字符串由以下数字依次组成：a_1, a_2, a_3, ..., a_n。在递归方法中，我们创建一个字符串如下："a_1" + "a_2" + .... + "a_n"。在迭代方法中，我们做：(((...(a_1) + a_2) + a_3) + ... + a_n)))...)。因此，两种情况下的时间复杂度在 O(n^2) 时应该相同（在 C++03 中。请参阅下面的 C++11 注释）。

如您所见，这两种方法都深受实施细节的影响。 string 类型对于涉及重复连接的操作不是很有用。如果你有一个大小为 n 的预分配数组，你可以将复杂度降低到 O(n).

注1：追加操作有一些细节。在 C++03 中，追加操作没有特定的复杂性，可能导致 Copy-On_write（如果字符串不能就地扩展并且需要重定位）。在 C++11 中，CoW 和 rope-style 实现是不允许的，附加应该导致每个字符的分摊 O(1) 时间。因此，在 C++11 的情况下，我们应该能够获得两种实现的 O(n) 时间复杂度。

注释 2：要使用 user-defined 字符串实现（包含长度）获得 O(n) 时间复杂度，字符串需要通过函数中的引用。这将导致函数签名更改为：

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

如果字符串使用 pre-allocated.

数组，此实现将使字符串共享和更新 in-place

Answer 2

注：

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

编辑后的答案：

由于 return 值必须包含输出，因此无法获得比 O(n).

更好的 space 复杂度

假设输出字符串由以下数字依次组成：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 中 this answer 表示某些追加操作可以优化为单个字符摊销 O(1)。假设这是真的，写出的迭代版本将具有 O(1) 时间复杂度，无需任何额外工作。

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

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

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

Recursive base conversion time complexity analysis

c++

algorithm

recursion

numbers

base

索赔：

推理：

注：

编辑后的答案：