雙metaphone算法的最佳/最差/平均時間效率是多少？

我正在查看Double Metaphone算法。我只是想計算算法的效率等級。這裏在Python。這是我能找到的最具可讀性的代碼。雙metaphone算法的最佳/最差/平均時間效率是多少？

我不是一個很好的分析算法的時間，但我知道這個算法中的while循環應該花費最多的時間。在這種情況下，程序會在一個字符串的每個字符，從左至右依次爲：

while pos <= last :

我會假設，這將需要n步，其中n是字符串的長度。

但是，該算法在這個循環中有很多'if'和'elif'語句;我不知道他們是否會顯着影響時間。任何人都可以通過這個指導我？我想通過求和來計算時間效率。

爲了試圖回答我自己的問題，我認爲它的最佳效率是長度爲1的字符串，它必須輸入儘可能少的'if'語句。另一方面，最壞的情況可能只是一個非常長的字符串。

謝謝！

來源

2012-04-28 TimeBomb006

它看起來像你不小心省略了你所指的代碼。 – 2012-04-28 23:01:28

@David它在鏈接，它真的很長，所以可能會更好，它不被張貼 – dfb 2012-04-28 23:03:57

起初我讀這個作爲「雙比喻算法」，現在我只是失望，可能是什麼 – 2012-04-28 23:10:19

沒有看每一個條件，這看起來是線性的。下面有一些例外的簡單規則是，如果/ then語句不影響算法的漸近運行時間，除非它們執行某種循環或遞歸。我看到的所有東西看起來都是恆定時間的操

如果我真的需要確定的話，我會如何處理它。如果它不是直截了當地依賴於條件語句，你需要找一些事情

break語句和改變控制流動其他的事情 - 這可能會減少漸近時間
在變量的不規則修改while或for聲明，這可能會使算法花費更多時間。在這裏，這意味着pos或last被修改。

這不是一個全面的列表，但它可能會幫助你。

來源

2012-04-28 23:02:55 dfb

我認爲這可能是案子。我不太瞭解Python，但是我發現它是該算法最具可讀性的源代碼，因爲沒有很好的僞代碼。據我所知，除while循環以外的任何事情都不會超過常量，但我想確保。謝謝！ – TimeBomb006 2012-04-28 23:08:49

在相關說明中，我不太瞭解如何向此腳本輸入字符串。筆者注意到這個用法：'dm（string） - >（string，string或None）'。作爲一名新手Python用戶，我不知道如何運行它。我試過'python metaphone.py dm（stringHere）'沒有運氣。我的無知正在顯現。 – TimeBomb006 2012-04-28 23:25:13

嘗試使用-c標誌。 python -c'打印1 + 1'。更好的是，只需編寫一個腳本並將'import '寫入代碼並運行即可 – dfb 2012-04-28 23:27:31

雙metaphone算法的最佳/最差/平均時間效率是多少？

回答

相關問題