python - 我的后缀数组生成代码的时间复杂度是多少

Question

我正在尝试使用 python 语言创建一个后缀数组。我的程序没有通过所有测试用例并显示超时错误。我认为它的时间复杂度是 O(N logN logN)。这是我的代码：

def criteria1(s):
    return s[0]


def criteria2(s):
    return s[1]


def criteria3(s):
    return s[0][0]


text='banana'
l=len(text)
s=[]            
for i in range(l): 
    s.append([[ord(text[i])-ord('a'),None],i]) # s is list of [[rank1,rank2],original_index] where rank1 is set according to first character of suffices of 'text'

doTill=1
while doTill<l:
    for i in range(l): # assigning the second rank
        try:
            s[i][0][1]=s[i+doTill][0][0]
        except IndexError:
            s[i][0][1]=-1

    s.sort(key=criteria1)  # sorting based on [rank1,rank2]
    #print('first sort',s)
    temp=list(s[0][0])     # now assigning new rank1 based on [rank1,rank2]
    s[0][0][0]=0           # setting rank1 of first element to 0
    r=0
    for i in range(1,l):
        if temp==s[i][0]:
            s[i][0][0]=r
        else:
            temp=list(s[i][0])
            r+=1
            s[i][0][0]=r
    #print('reassign ranks',s)
    s.sort(key=criteria2)    # again sorting based on original_index of suffices
    doTill*=2
s.sort(key=criteria3)        # now getting the required suffix array from s by first sorting it according to rank1 and then getting original_indices
for i in range(l):
    s[i]=s[i][1]
print(s)

请提供建议以改进我的代码及其时间复杂度。提前致谢

标签： pythonalgorithmdata-structuressuffix-array