2

您好，感谢您的阅读。我正在做家庭作业。我创建了一种与字符串进行比较的方法，以查看一个是否是另一个的子字符串。我知道已经有一个内置的方法可以做到这一点。作业不允许我使用它们。无论如何，下面的代码正在工作。

我必须使用 Big-O 表示法来分析算法的复杂性。从我可以看到外循环以线性时间运行，因为它只是运行与字符串长度一样多的时间。因此：O(n)

内部循环是不同的，它可能会发生也可能不会发生，如果发生，它可能会在它输入的第二个字符串的长度之前完成。因此：O(logn)

所以在我看来复杂度是 O (n*logn)。这会简化为 O(n) 还是保持当前形式？或者我错了内循环是O（logn）？

import java.util.Scanner;

public class HW3q6 {
public static void main(String[] args) {
    Scanner userInput = new Scanner( System.in );
    System.out.println("Please enter the first string: ");
    char[] charArray1 = userInput.nextLine().toUpperCase().toCharArray();
    System.out.println("Please enter the second string: ");
    char[] charArray2 = userInput.nextLine().toUpperCase().toCharArray();

    System.out.println("The second string is a substring of the first: " + subString(charArray1, charArray2));

}

private static boolean subString(char[] charArray1, char[] charArray2) {
    int counter = 0;
    for (int i = 0; i < (charArray1.length + 1) - charArray2.length ; i++) {
        if (charArray1[i] == charArray2[0]) {
            for (int n = 0; n < charArray2.length; n++) {
                if (charArray1[i+n] == charArray2[n]) {
                    counter++;
                }
            }
            if (counter == charArray2.length) {
                return true;
            } else
                counter = 0;
        }
    }
    return false;

}
}
4

4 回答 4

2

我看到你已经接受了一个答案。但是您的时间复杂度实际上是较小的文本和较大的文本O(m*(n-m+1))在哪里。要看到这种区别很重要，只需为 m 和 n 选择几个数字并计算。如果论点是当谈到 Big-O 表示法时和since之间没有太大区别，那么您可以说复杂度是since 。此外，您的代码没有进行正确的错误检查，请参阅Geekviewpoint.com 关于字符串匹配的一些提示。mnO(mn)O(m*(n-m+1))O(mn) > O(m*(n-m+1))O(n^2)O(n^2) > O(mn) > O(m*(n-m+1))

于 2013-01-30T23:29:52.027 回答
2

内循环不是 logN。Big O 衡量最坏情况的复杂性。正如我从您的代码中了解到的那样，内部循环可以运行 N（字符串长度 2）次。解释如下：

假设你有两个字符串 aaaaaaaa 和 aaac，外循环会匹配第一个字符，你会进入内循环，检查每个字符，然后实现一个 false。然后外循环将再次将第二个字符串的开头与第一个字符串的第二个字符匹配，然后您将再次检查第二个字符串中的所有字符是否为假。这将适用于第一个字符串的 M 个字符，以及第二个字符串的 N 个字符，产生一个 O(MN) 算法，考虑到 M=c*N，它是 O(N^2)，其中 c 是一个常数。

希望这可以帮助。

于 2013-01-30T23:01:45.030 回答
1

正如 mellamokb 指出的那样，内部循环仍然以线性时间运行。因此，您的算法作为一个整体将是 O(mn)，其中 m 和 n 是两个字符串的长度。

于 2013-01-30T23:00:21.947 回答
1

O(NlogN)不等于O(N)

但是，您认为内部循环是错误的推理O(logN)是错误的。它“可能会发生也可能不会发生”的事实并不一定会成功O(logN)。例如，如果内部循环发生“平均大约一半的时间”，那么贡献可能是C * 1/2 N; 即O(N)。

我现在没有时间详细分析代码，但您似乎需要查看最佳、平均和最坏情况的复杂性。

（例如，快速排序算法的经典形式，O(NlogN)平均而言，但最坏情况的复杂度为O(N^2).）

于 2013-01-30T22:43:05.833 回答