该算法的大 O 表示法是什么

Question

判断字符串是否包含至少1个可重复字符。

（暗示该字符串只能包含基本的 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) for str.length() <= 128，其中 n - 字符串的长度
• O(1) 对于 str.length() > 128

但是摊销后的大 O 值是多少？

---

P.S.

也可以使用某种数据结构（例如map）代替排序，它将操作量减少到O(n)，但会增加内存成本。反正和问题无关

Answer 1

严格来说，这个算法的时间复杂度是O(1)，因为运算次数T(n)不依赖于输入的大小（对于足够大的n）并且受一些常数操作的限制。

Answer 2

算法的amortized analysis应该基于预期的输入。

在你的情况下——没有任何关于预期输入长度分布的先验知识——你无话可说。

换句话说 - "amortized complexity" 项没有关于输入的假设对你的算法没有多大意义。