去年我一直在研究 DSA 和 Big O 分析，但我一直在努力計算這個時間復雜度。這是來自練習，但為了簡單起見，我只是隔離了導致我困惑的原因。
希望有人能給我一些指導。
這是要分析的小代碼，當我展示示例時，我將更改單詞和前綴資料。
String prefix = "TAXI";
String word= "TAXI";
while (word.indexOf(prefix)!=0){
prefix= prefix.substring(0,prefix.length()-1);
}
只是為了澄清：
- Java 中的 IndexOf 是 (N * M )
- 子字串在 Java 中是 (N)
- 從現在開始，M 是前綴的長度，N 是單詞的長度
方案 1
前綴與 Word 相同：
String prefix = "TAXI";
String word= "TAXI";
while (word.indexOf(prefix)!=0){
prefix= prefix.substring(0,prefix.length()-1);
}
While回圈執行的次數=0；
盡管 IndexOF 具有 (N * M ) 復雜性，但我們知道我們將進行 M 次比較。
N[0] == M[0] N[1] == M[1] N[2] == M[2] N[3] == M[3]
我們可以說這是最好的情況 = O(M)
方案 2
前綴和單詞只共享第一個字母
String prefix = "TAXI"; - > Length = 4
String word= "TXXXXXXX"; - > Length = 8
while (word.indexOf(prefix)!=0){
prefix= prefix.substring(0,prefix.length()-1);
}
- IndexOf執行的次數= 4 ，所以 M 次
- While 回圈執行的次數= 3 ，所以 M 次 - 1
讓我們想想 IndexOf 每次執行的實際比較次數：
- 出租車 - > 索引，比較次數 9
- Tax- > Index of , 比較次數 8
- Ta- > Index Of , 比較次數 7
- T- > Index Of , 比較次數 1
總比較 = 26
我們可以說總數是 = (N * M - M 1) ，去掉常數 = > (N * M - M) = > (N * M)
Substring方法呢？會執行 3 次，每次都會執行這個比較次數：
- (M) 比較
- (M - 1) 比較
- (M - 2) 比較
所以，(M) (M-1) ( M -2) = M*(M 1)/2。= O (M * M)
現在我們有了全貌，最壞的情況（目前）是：BIG O (N * M M2)
方案 3
前綴存在，但從不在 0 位置：
String prefix = "TAXI"; = > Length = 4
String word= "XXTAXI"; = > Length = 6
while (word.indexOf(prefix)!=0){
prefix= prefix.substring(0,prefix.length()-1);
}
- IndexOf執行的次數= 4 ，所以 M 次
- While 回圈執行的次數= 3 ，所以 M 次 - 1
讓我們想想 IndexOf 每次執行的實際比較次數：
- Taxi -> Index of , 比較次數 6
- Tax- > Index of , 比較次數 5
- Ta- > Index Of , 比較次數 4
- T- > Index Of , 比較次數 3
現在我遇到了一個問題，我發現了兩種不同的方式來表達這個問題：
- 總比較 = (N) (N-1) (N-2) (N -3) = N*(MN1)/2。= O (N * N)
或者我可以認為比較的數量如下所示：
(N - M- M) ( N - M - M 1 ) (N -M - M 2 ) ( N - M - M 2) = (6 - 0 ) ( 6 - 1 ) (6 - 2) (6 - 3)
= > (N * M - (something)) = > 移除常數 > (N * M)
那么，對于這種情況，哪個是正確的 Big o？(N * M M2 ) 或 (N * N M2 )
場景 4 - 最后一個
情景最差指數。
String prefix = "TTTK"; = > Length = 4
String word= "TTTTTK"; = > Length = 6
while (word.indexOf(prefix)!=0){
prefix= prefix.substring(0,prefix.length()-1);
}
在另一個字串中搜索字串時，這是最壞的情況，您實際上應該使用所有組合。
- IndexOf執行的次數= 2
- While 回圈執行的次數= 1
在這個例子中，第一次它必須做 N * M 個真正的組合，這幾乎是所有，因為由于 Substring 洗掉了 Prefix 的最后一個字符，現在，它第二次將執行索引，它只會需要執行 M 次操作，它會以最快的方式找到子字串。
讓我們想想 IndexOf 每次執行的實際比較次數：
- TTTK-> 的索引，N * M
- TTT-> 指數, M
子字串只會運行 1 次 M 次 = > O(M) 。
在這種情況下，我得到的最后一個大 O 是 = (N M M ) M > 移除常數 = N M
我的兩個大問題是：
- 4 分析是否正確？
- 第二個場景是否是最壞情況的復雜性？
先感謝您！
uj5u.com熱心網友回復：
你的推理有問題。您正在嘗試提出過于具體且字串太小的場景。時間復雜度對于確定演算法所花費的時間如何隨著輸入大小的增長而增長很有用。
要回答您的問題：
- 只要比較結果的數量是正確的，您的分析就是正確的（對于場景 3，您的方程式對我來說沒有意義，但復雜性將是
O(N*M M^2)，原因與場景 2 中或多或少相同）； - 不，您的方案 2 并不是最壞的情況。
最壞的可能情況是回圈運行O(M)多次，每次執行一次indexOfinO(N*M)和一次substringin O(M)，使得整體時間復雜度為O(M*N*M M*M) = O(N*M^2)。
這是最壞情況的一個例子。考慮一個由M/2字母乘以A后面跟著字母乘的前綴，以及由字母M/2乘以構成的B單詞。NA
String prefix = "AAA...BBB"; // length M
String word = "AAAAA..."; // length N
因為單詞中只包含一半前綴，所以回圈將運行M/2時間（洗掉所有出現的B）。條件將被評估M/2 1次數，但這 1在整體復雜性中并不重要。
每次indexOf都執行操作，對單詞中的每個字母（除了最后一個，但如果 沒有關系）進行M/2比較（前綴中的所有字母），時間復雜度為.AM/2-1N > M/2O(N*M/2) = O(N*M)
每次都substring對前綴執行操作，其大小在M和之間變化M/2，時間復雜度為O(M)。
因此，本例中的總時間復雜度為M/2 * (O(N*M) O(M)) = O(N*M^2)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520451.html
標籤：算法时间复杂度大哥
上一篇：python中有沒有一種方法可以在沒有if-else邏輯的情況下執行像'formin（x，y）doz'這樣的陳述句？