optmise此代碼最小運行時間

-4

def main(): 
    inp=raw_input() 
    x=list(inp.split()[0]) 
    y=list(inp.split()[1]) 
    if (len(x)==len(y)): 
     if (set(x)==set(y)): 
      return "YES" 
     else: 
      return "YES" 
    else: 

     if(set(x)==set(y)): 

      return "NO" 
     else: 
      return "YES" 

main()

我需要的最短運行時間，任何幫助嗎？我不知道如何在漸近記法表示此...optmise此代碼最小運行時間

來源

2013-02-27 Ajay

它有一個O（1）的運行時間。關於代碼沒有什麼複雜的，雖然有一些分支是多餘的（不管這兩個集合是否等價，都會返回「YES」）。 – Makoto 2013-02-27 19:18:42

它使用3.9M \t我可以以某種方式進一步減少 – Ajay 2013-02-27 19:20:18

也許你應該告訴我們你在做什麼。 – 2013-02-27 19:21:05

刪除所有重複和不必要的工作會刮鬍子關閉一點點。請不要在inp上撥打split()兩次，也不要在結果相同的情況下創建並比較set，等等。另外，如果您唯一要做的事情不需要將str轉換爲list與他們做的是檢查他們的len並將他們變成set s。所以：

def main(): 
    x, y = raw_input().split()   
    if len(x)==len(y): 
     return "YES" 
    else: 
     if set(x)==set(y): 
      return "NO" 
     else: 
      return "YES"  
main()

真的沒有辦法讓Python在Python中顯着更快。

漸近運行時間顯然是O(N)，其中N是輸入字符串的長度。你正在做一堆線性長度的東西（split，複製前半部分，複製後半部分，在每半部分中製作set等等），而且沒有超線性的東西。

從理論上講，通過使用大小爲256的位集而不是集合，您可以更快速地完成任務，而且內存更少。下面是一些僞代碼：

matches = [0 for i in range(256)] 
for char in x: 
    matches[char] = 1 
for char in y: 
    if matches[char] < 1: matches[char] = -1 
    else: return "YES" 
for match in matches: 
    if match == 1: return "YES" 
return "NO"

這當然仍然是線性的，同時也減少了直線步數，並允許您短路早些時候在許多情況下，再加上你刪除「貴」與「賤」散列（它在C中實際上不存在，因此是免費的）。所以，它與更小的乘數成線性關係。

我預計，在實踐中，這將是在Python一大堆慢，因爲在翻譯的C代碼中100種元素的隱式循環（例如，set構造函數）是速度遠遠超過了一個Python顯式循環即使你中途短路。但是，如果您將其編碼爲C擴展名，則可能會比使用set更快。

如果您試圖避免記憶，請注意上述解決方案並不要求您一次讀取整件事情。例如，代替for char in x:和for char in y:，執行for char in unsplit_string:，然後再輸入if char.isspace(): break，然後再輸入for char in unsplit_string:。

但是，這並不能真正幫助任何事情，因爲raw_input已經必須將整個事件一次讀入內存。因此，如果您閱讀的字符串足夠大，則可能需要更改爲sys.stdin.read。（關閉輸入緩衝並一次讀取1個字節顯然會給你提供最好的內存使用，但可能會讓事情變得非常慢，所以你需要權衡。通常，讓Python/stdio使用默認緩衝區就足夠了。）

來源

2013-02-27 19:23:06 abarnert

optmise此代碼最小運行時間

回答

相關問題