这个基本转换器的 Big-O 是什么？

Question

我的答案是O(D + R)。正确吗？

我想弄清楚这段代码的大O。我正在做一个关于数据结构和算法的独立课程。

此代码摘自 L Groiner 女士的书 "Data Structure and Algorithms in JavaScript"，PacktPub，我正在研究这本书。

请看下面：

function baseConverter(decNumber, base) {
   var remStack = new Stack(), //instantiate class, define variable, O(1)
   rem, // define var, O(1)
   baseString = '', //initialize, O(1)
   digits = '0123456789ABCDEF'; //initialize, O(1) 

   while(decNumber>0) { //loop, D times:
       rem = Math.floor(decNumber % base); //modulo/Math/assignment, O(1) 
       remStack.push(rem); //push to stack, O(1)
       decNumber = Math.floor(decNumber / base); //divide, Math, assignment, O(1)
   }


   while(!remStack.isEmpty()){ //loop, R times: 
       baseString += digits[remStack.pop()]; //pop/index/Math/addition assignment, O(1)
   }
   return baseString; // O(1)
}

我逐行简化每个操作，如下所示：

4 * O(1) + D * 3 * O(1) + R * O(1) =
3 * O(D) + 1 * O(R) =
O(D) + O(R) = O(D + R)

我查阅了自己的 Web 开发笔记并阅读了各种书籍。但我只能形成片段并从中推断出来。我想找到一个标准化的框架，或者至少在我的脑海中构建它，以便能够在 Big-O 中正确陈述运行时间。给我反馈，帮助我这样做。

Answer 1

第一个循环的运行时复杂度：

 while (decNumber > 0) {
       rem = Math.floor(decNumber % base);
       remStack.push(rem);
       decNumber = Math.floor(decNumber / base);
 }

此循环的迭代次数为 decNumber 可以除以 base。因此，迭代次数大致为log_base(decNumber).

在每次迭代期间，您执行数组推送操作。 For simplicity we assume it runs in constant time。

第二个循环的运行频率与数组元素被推入 remStack 的频率相同，这等于第一个循环的迭代次数。

因此，总体运行时复杂度大致与 2 * log_base(decNumber) 成正比，即 O(log(decNumber))。

只要 decNumber 上的模和除运算可以在典型硬件上以恒定时间执行（这对于有限精度 JavaScript 数字数据类型是正确的）就成立。

这个基本转换器的 Big-O 是什么？

What's the Big-O of this base converter?

javascript

algorithm

big-o

stack