如何确定python代码的复杂性

Question

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

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

正如我所提到的，您的isPalindome函数实际上是不正确的，因为您没有更改索引。我也改变了你的一些，所以这是我正在分析的版本。(我只是在分析isPalindome函数，因为我实际上不明白主函数在做什么(，对不起！

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(，其中N是数字。这是因为平均而言，if比较有50%的机会中断(返回False(，50%的机会继续。因此，预期的比较次数为|n|/4，即O(|n|(。