Python3.x - 使用字典

-1

鑑於一些串S的所有子計數出現次數，該代碼將計算該字符串的所有可能的子串出現的次數S.Python3.x - 使用字典

#count[i]=no of different substrings in the string that occurs exactly i times 
count=[0]*(100001) 
a=input() 
dic={} 
n=len(a) 
for i in range(n): 
    temp="" 
    for j in range(i,n,1): 
     temp+=a[j] 
     if temp in dic: 
      dic[temp]+=1 
     else: 
      dic[temp]=1 
for k,v in dic.items(): 
    count[v]+=1

例如，對於字符串「巴」，陣列將是：

CNT [1] = 4 { 「巴」，「ABAB」，「巴巴」，「BAB」}出現一次
CNT [2] = 4 { 「aba」，「ab」，「ba」，「b」}恰好出現兩次
CNT [3] = 1 { 「一」}正好出現三次
CNT [4] = 0
CNT [5] = 0

我很興趣知道我的代碼

運行時

來源

2015-06-19 suren99

你只是問這會表現如何？如果是這種情況，那麼你應該自己測試一下，看看它的工作情況。 – SuperBiasedMan

哪裏有'temp'定義/分配？而'n'？ – Pynchia

複雜性不會根據字符串長度而改變，對於「foobar」最糟糕的情況是什麼？ –

基本上有兩個部分代碼的單獨考慮：

嵌套的循環，你建立`dic`。
建立`count`的循環。

對於1.有兩個循環要考慮。 i循環將運行n次，j循環將每次運行n-i次。

這意味着j循環將運行在第一時間n次，第二次n-1倍，以此類推，直到它運行一次i = n-1時。因此該塊的總運行時間爲n（n + 1）/ 2，即O（n^2）。

（注：我假設詞典訪問需要大多數時間都是恆定的時間）。

For 2.只有一個循環需要考慮哪個將運行多少次唯一的子串存在。對於長度爲n的字符串，唯一子字符串的最大數目也是n（n + 1）/ 2，這也是O（n^2）。

所以，運行時間是O（n^2）。對於n = 10e5，使用標準假設10e9操作需要1秒鐘，操作次數爲〜10e10，大約需要10秒。

來源

2015-06-19 20:51:01 Rishav

爲字符串「AAAAA ......一個」結束該子（長度= 5000）它大約需要37秒。爲什麼？ – suren99

因爲「我假設字典訪問需要不斷的時間」 – Rishav

@ suren99請參閱https://wiki.python.org/moin/TimeComplexity#dict – Rishav

Python3.x - 使用字典

回答

相關問題