数字の次の最大の回文を見つける2つのアプローチの複雑さ

Question

次の最大の回文についてオンラインで問題が発生しました。私はPythonで2つの異なるアプローチで問題を解決しました。一つ目は、

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の長さです）。