找到下一個最大回文數的兩種方法的複雜性

Question

我已經想出了一個關於下一個最大回文數的問題，我已經通過python中的兩種不同方法解決了這個問題。第一個是，

t = long(raw_input()) 

for i in range(t): 
    a = (raw_input()) 
    a = str(int(a) + 1) 
    palin = "" 
    oddOrEven = len(a) % 2 

    if oddOrEven: 
     size = len(a)/2 
     center = a[size] 
    else: 
     size = 0 
     center = '' 

    firsthalf = a[0 : len(a)/2] 
    secondhalf = firsthalf[::-1] 
    palin = firsthalf + center + secondhalf 

    if (int(palin) < int(a)): 
     if(size == 0): 
      firsthalf = str(int(firsthalf) + 1) 
      secondhalf = firsthalf[::-1] 
      palin = firsthalf + secondhalf 

     elif(size > 0): 
      lastvalue = int(center) + 1 

      if (lastvalue == 10): 
       firsthalf = str(int(firsthalf) + 1) 
       secondhalf = firsthalf[::-1] 
       palin = firsthalf + "0" + secondhalf 

      else: 
       palin = firsthalf + str(lastvalue) + secondhalf 
    print palin 

和另外一個是，

def inc(left): 
    leftlist=list(left) 
    last = len(left)-1 
    while leftlist[last]=='9': 
     leftlist[last]='0' 
     last-=1 

    leftlist[last] = str(int(leftlist[last])+1) 
    return "".join(leftlist) 


def palin(number): 
    size=len(number) 
    odd=size%2 
    if odd: 
     center=number[size/2] 
    else: 
     center='' 
    print center 
    left=number[:size/2] 
    right = left[::-1] 
    pdrome = left + center + right 
    if pdrome > number: 
     print pdrome 
    else: 
     if center: 
      if center<'9': 
       center = str(int(center)+1) 
       print left + center + right 
       return 
      else: 
       center = '0' 
     if left == len(left)*'9': 
      print '1' + (len(number)-1)*'0' + '1' 
     else: 
      left = inc(left) 
      print left + center + left[::-1] 

if __name__=='__main__': 
    t = long (raw_input()) 
    while t: 
     palin(raw_input()) 
     t-=1 

作爲計算機科學的角度看，什麼是雙方的這種算法的複雜性？哪一個更有效？

Answer 1

我看到你正在for循環中創建一個子列表，而最大的子列表的大小爲n-1。然後循環到n。

所以最壞的情況是O（n^2），其中n是t的長度。