如何确定python代码的复杂度？

Question

我需要了解以下代码的复杂性。我熟悉所有Big O()符号的概念，也读过很多博客，但我不知道如何将其应用于大型程序。以下是从100到999的最大回文号码的代码：

def isPaindrome(number):
    stringNum = str(number)
    firstDigit_index,lastDigit_index=0,len(stringNum)-1
    isPalindrome = False
    while(lastDigit_index > 0 and firstDigit_index < lastDigit_index):
        #print(stringNum[f],"==",stringNum[l],"......")
        if(stringNum[firstDigit_index]==stringNum[lastDigit_index]):           
            isPalindrome = True
        else:
            isPalindrome = False
            break
        firstDigit_index = firstDigit_index + 1
        lastDigit_index = lastDigit_index - 1

    if(isPalindrome):
        return number
    else:
        return 0

max = 0
startRange = 100
endRange = 999
for i in range(endRange*endRange,startRange*startRange,-1):
    factors = []
    result = isPaindrome(i)
    if(result!=0):
        for i in range(startRange,endRange+1):
            if(result%i==0):
                factors.append(i)
        if(len(factors)>1):
            sumFactor = factors[(len(factors))-1] + factors[(len(factors))-2]
            mul = factors[(len(factors))-1] * factors[(len(factors))-2]
            if(sumFactor>max and mul==result):
                max = sumFactor     

                print("Largest Palindrome made from product of two 3 digit numbers(",factors[(len(factors))-1],",",factors[(len(factors))-2] ,") is", result,".")

如果有人能一步一步地教我如何计算，我将不胜感激。

Answer 1

正如我所提到的，您的isPalindrome函数实际上是不正确的，因为您没有更改索引。我也对你的版本做了一些修改，所以这就是我正在分析的版本。(我只是在分析isPalindrome函数，因为我实际上不能理解main函数在做什么)，对不起！

def isPalindrome(n):
  num = str(n)
  head, tail = 0, len(num) - 1
  while tail > head:
    if num[head] != num[tail]: # Not symmetrical!! WARNING!
      return False
    head += 1 # move position
    tail -= 1 # move position
  return True

该代码平均为O(|n|)，即O(log )，其中N是数字。这是因为平均而言，if比较有50%的机会打破(返回False)，50%的机会继续。因此，预期的比较次数为|n|/4，即O(|n|)。