一些递归和 none 递归算法的时间复杂度

Question

我有两个伪代码算法：

RandomAlgorithm(modVec[0 to n − 1])
b = 0;
for i = 1 to n do
  b = 2.b + modVec[n − i];
for i = 1 to b do
  modVec[i mod n] = modVec[(i + 1) mod n];
return modVec;

第二个：

AnotherRecursiveAlgo(multiplyVec[1 to n])
if n ≤ 2 do
  return multiplyVec[1] × multiplyVec[1];
return
  multiplyVec[1] × multiplyVec[n] + 
  AnotherRecursiveAlgo(multiplyVec[1 to n/3]) + 
  AnotherRecursiveAlgo(multiplyVec[2n/3 to n]);

我需要分析这些算法的时间复杂度：对于我得到的第一个算法，第一个循环在 O(n) 中，第二个循环有一个最好的情况和一个最坏的情况，最好的情况是我们有 O(1) 循环运行一次，最坏的情况是我们有一个很大的n 在第一个循环中，但我不知道如何将这个想法写成时间复杂度，因为我通常得到 b=sum(from 1 to n-1) of 2^n-1 。 modVec[n-1] 我卡在这里了。

对于第二个循环，我只是不知道如何解决这个循环的时间复杂度，我们通常让它依赖于 n ，所以我们需要我认为的公式。

感谢您的帮助。

Answer 1

第一个问题有点奇怪，好吧。如果有帮助，请将 modVec 设想为 1 和 0 的数组。在这种情况下，第一个循环将此数组转换为一个值。这是 O(n)

例如，(1, 1, 0, 1, 1) 将产生 b = 27。

您的第二个循环运行 b 次。 b 值的主导项是 2^(n-1)、a.k.a。 O(2^n)。您在循环内所做的分配是 O(1).

第二个循环依赖于 n。您的基本情况是一个简单的乘法，O(1)。递归步骤有三项：

简单乘法
在 n/3 个元素上重复出现
在n/3个元素上重复（从2n/3到最后是n/3个元素）

正如您的二进制分区导致 log[2] 复杂性一样，这个将导致 log[3]。基础无关紧要；系数（两次递归调用）无关紧要。 2*O(log3) 仍然是 O(log N).

这会促使您找到解决方案吗？

Answer 2

第一个循环

对我来说，这归结为 O(First-For-Loop) + O(Second-For-Loop)。

O(First-For-Loop) 很简单 = O(n)。

O(Second-For-Loop) 有趣地取决于 n。因此，对我来说，它可以描述为 O(f(n))，其中 f(n) 是 n 的某个函数。不完全确定我是否根据所提供的代码理解 f(n)。

答案因此变为 O(n) + O(f(n))。这可以归结为 O(n) 或 O(f(n))，具体取决于哪个更大且更占主导地位（因为低阶项在大 O 表示法中无关紧要。

第二个循环

在这种情况下，我看到每次调用该函数都会调用 3 个额外的调用...

第一个调用似乎是一个 O(1) 调用。所以没关系。

第二次和第三次调用似乎递归函数。因此，每个函数调用都会导致 2 个额外的递归。

因此，时间复杂度为 O(2^n)。

一些递归和 none 递归算法的时间复杂度

time complexity of some recursive and none recursive algorithm

algorithm

recursion

pseudocode

time-complexity

data-structures