【求问】时间复杂度分析的疑问

a49481 发表于 2022-9-20 19:34
String.equals确定是O(1)吗？我第一次见到这种说法，能给个出处不？

public boolean equals(Object anObject) {
    if (this == anObject) { // O(1)
        return true;
    }
    if (anObject instanceof String) //O(1)  {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) { // O(1)
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {  // O(n)
                if (v1[i] != v2[i]) //O(1)
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

a49481 发表于 2022-9-20 18:34
String.equals确定是O(1)吗？我第一次见到这种说法，能给个出处不？

是O(n), n是String长度没错. 但在整个算法里 这个n是可以忽略不计的, 就是O(n). 这没啥出处. 没有任何一道题, 或者任何一个面试官会去考虑 String.equals()对于算力的影响. 至于最后是O(n)还是O(1)讨论都没有意义. 我说O(1)就是可以忽略不计的意思. 我觉得我说的够明白了. 如果你有不同意见我尊重你的意见.

icebane 发表于 2022-9-20 19:44
是O(n), n是String长度没错. 但在整个算法里 这个n是可以忽略不计的, 就是O(n). 这没啥出处. 没有任何一 ...

leetcode里的大部分题目是因为字符串长度有限制，例如少于20个字符，自然不需要考虑String.equal的复杂度，毕竟最多也就是个常数20，这种题目重点也不在字符串上

考字符串的题目里边还是得仔细考虑一下String.equal的复杂度，最简单的例子是如果把String.equal当成O(1)的，KMP算法就没有存在必要了，直接拿S的每个子串去和T判断是否相等就是个线性的字符串匹配算法

你说的这些全都要计算在内，虽然java仅需要一行来实现，也是要考虑内部的复杂度

只需要记住这一点就好：时间复杂度是衡量时间随问题规模增长的函数，因此任何步骤，只要其运行时间随问题规模一同增长，就要考虑进时间复杂度

当然题做的多了，大部分O(1)的操作就直接忽略了，就可以一眼看出哪个操作是影响时间复杂度的核心步骤

icebane 发表于 2022-09-20 17:44:05
是O(n), n是String长度没错. 但在整个算法里 这个n是可以忽略不计的, 就是O(n). 这没啥出处. 没有任何一道题, 或者任何一个面试官会去考虑 String.equals()对于算力的

当然是要考虑的，不然很多题里字符串hash，后缀数组这种东西都没有意义了，还有楼上说的kmp也没有意义了

要记录的，你想，2 sum排序后双指针的解法，如果不计算排序的开销，那不就时间空间复杂度同时是最优解了……