java大O:O（n）的比较

Question

下面的算法比较两个字符串，如果相同，则返回0，否则返回

是运行时间O（n），因为for循环取决于两个字符串的最小长度n

int compareStrings(String s1, String s2) {
    int n = min(s1.length(), s2.length());
        for (int i=0; i<n; i++) {
        if (s1.charAt(i) != s2.charAt(i)) {
            return s1.charAt(i) – s2.charAt(i);
        }
    }
    return s1.length() – s2.length();
}

Answer 1

是的，是O（n）

@LouisWasserman:如果我使用合并排序算法和compareStrings方法，如果只有1个字符串需要比较，那么最好的情况是（logn）时间吗？我知道合并排序的最坏情况是O（n logn）

这里有两个不同的n：一个表示字符串的长度，另一个表示正在排序的字符串的数量。如果要排序的字符串长度为m，则合并排序作为一个整体将花费O（nm log n）时间路易斯·沃瑟曼