如何确定一个简单回文R代码的时间复杂度？

Question

我很新手，不太懂如何计算算法或代码的时间复杂度，所以我不确定这个函数的复杂度是什么：

isPalindrome <- function(num){
  if(num < 0) return(F)
  rev <- 0
  orig_num <- num
  while(num != 0){
    pop <- num %% 10
    num <- num %/% 10
    rev <- rev*10 + pop
  }
  if(orig_num == rev) return(T)
  else return(F)
}

调用函数，例如isPalindrome(122221)，将返回TRUE。 基本的想法是计算反向数字，然后将其与原始数字进行比较，如果它们相等，则它是回文数。

我的基本直觉是为了计算反向数字，while循环将遍历每个数字，所以对于一个4位数，如1221，将有4个动作需要完成（每个动作需要一些执行时间），因此如果我的数字相对于其数字变为2倍，则例如12222221，则我需要完成8个动作。然后，我的输入增加了2倍，时间也增加了2倍，因此时间复杂度应为O(n)。这正确吗？

- Corel

---

我非常确定这只是O(n) - 只有一个循环，它遍历数字的每一位，所以它与数字的位数成正比，因此是O(n)。但是，相对于输入数字，它是O(floor(log10(n)) + 1)。因此，它取决于您想要根据什么进行测量。 - Geza Kerecsenyi

@Suren：为什么，干嘛？ - Corel

@GezaKerecsenyi：没错，我想将其与我的输入（最终是一个数字）进行比较，你能解释一下为什么这是O（floor(log10(n)) + 1）吗？这个数字本质上是由数字组成的，那么这两者如何在时间复杂度上有所不同呢？ - Corel

我的意思是说，你可以将数字转换为字符，然后轻松检查它是否为回文。我并没有评论时间复杂度。 - kangaroo_cliff

O(floor(log10(n)) + 1) 是数字计数函数：我们取该数字的 log10（即找到使得 $10^x=n$ 的 x 值）-例如 log10(10) = 1，log10(100) = 2，log10(1) = 1，log10(7) = 0.845...。然后我们向下取整，因为例如 14 (log10(14)=1.146) 和 11 (log10(11)=1.041) 中的数字位数相同。正如您所看到的，数字计数向下偏移了 1，因为我们是相对于 10 进行测量的。因此，我们在上面加上一个 1 来获取数字计数。由于它是一个 O(digits) 循环，我们只需将 floor(log10(n))+1 插入其中以获取相对于输入数字的最终大 O。 - Geza Kerecsenyi

Answer 1

你的直觉是正确的：相对于数字的位数，你的算法将以O(n)的时间复杂度运行。也就是说，与数字的大小相比较，它的时间复杂度为O(floor(log10(n)) + 1)，这是一个计算数字位数的函数。

- rikyeah