該算法的大O表示法是什麼

確定字符串是否包含至少1個可重複字符。該算法的大O表示法是什麼

（暗示字符串只能包含基本的ASCII字母：128個字符）。

bool hasRepeatableChar(String str) { 
    if (str.length() > 128) { 
      return true; 
    } 
    str = str.sort(); 
    for (int i = 0; i < str.length()-1; i++) { 
     if (str[i] == str[i+1]) { 
      return true; 
     } 
    } 
    return false; 
}

正如我所看到的，它是：

爲O（n log n）的爲str.length（）< = 128，其中n - 長度的字符串的
O（1）爲 str.length（）> 128

但是將是一個mort大O的價值？

P.S.

而不是排序它也可以通過使用某種數據結構（例如地圖）來完成，它會減少對O（n）的操作量，但會增加內存成本。無論如何，這與問題無關。

來源

2017-07-04 i.van

這是O（n日誌n） –

@MauricePerry但是爲什麼？對於某些範圍（0

由128個字符組成，它們可能表示字符串中允許使用哪些字符，而不是長度。 – fgb

嚴格地說，該算法的時間複雜度爲O(1)，因爲操作T(n)的數量並不取決於輸入的大小（足夠大n），並通過一些固定數量的操作界。

來源

2017-07-04 09:31:40 DAle

算法的amortized analysis應該基於預期的輸入。

在你的情況 - 沒有任何事先知道預期投入的長度分佈 - 你沒有多少可以說。

換句話說 - 沒有關於輸入假設的術語「攤銷複雜性」對於您的算法沒有多大意義。

來源

2017-07-04 09:39:18

該算法的大O表示法是什麼

回答

相關問題