r - 如何确定简单回文 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)。这个对吗？

标签： rtime-complexitybig-o

Answer 1

您的直觉是正确的：您的算法将O(n)根据数字的数字运行。也就是说，将其与数字的大小相比较，an O(floor(log10(n)) + 1)，即为数数功能。