子串串算法的大O分析。是否为O（n * LOGN）简化？ [英] Big-O analysis of a sub-string of string algorithm. Does O(n*logn) simplify?
问题描述
您好，感谢您的阅读。我工作的家庭作业。我已经建立了比较字符串，看一个是子串的另一种方法。我知道已经有一个内置的方法来做到这一点。的分配不会允许我使用他们。不管怎样，下面的code正常工作。
我要分析使用大O符号算法的复杂度。从我所看到的外循环运行线性时间，因为它只是运行多次字符串的长度。因此：O（N）
内循环是不同的，它可能会或可能不会发生，并且如果这样做，可能是它的输入，第二串的长度之前完成。因此：O（LOGN）
所以，在我看来，在复杂度为O（n * LOGN）。这是否简化为O（N）或它停留在目前的形式？还是我对内环为O（LOGN）错了？
进口java.util.Scanner中;
公共类HW3q6 {
公共静态无效的主要（字串[] args）{
扫描仪userInput =新的扫描仪（System.in）;
的System.out.println（请输入一个字符串：）;
的char [] charArray1 = userInput.nextLine（）与toUpperCase（）toCharArray（）。
的System.out.println（请输入第二个字符串：）;
的char [] charArray2 = userInput.nextLine（）与toUpperCase（）toCharArray（）。
的System.out.println（第二个字符串是第一个子：+子串（charArray1，charArray2））;
}
私有静态布尔子串（的char [] charArray1和char [] charArray2）{
INT计数器= 0;
的for（int i = 0;我≤（charArray1.length + 1） - charArray2.length;我++）{
如果（charArray1 [I] == charArray2 [0]）{
对于（INT N = 0; N＆LT; charArray2.length; N ++）{
如果（charArray1 [I + N] == charArray2 [n]）的{
反++;
}
}
如果（计数器== charArray2.length）{
返回true;
} 其他
计数器= 0;
}
}
返回false;
}
}
内环是logN个不是。大O测量最坏情况的复杂性。当我从你的code理解，内循环运行次数N（串2的长度）。说明如下：
假设你有两个字符串说AAAAAAAA和AAAC，外环将匹配第一个字符，你会去到内循环，检查每一个角色，进而实现一个假的。然后，外层循环将再次匹配第二个字符串与第一个字符串的第二个字符的开始，那么你将再次检查在第二个字符串中的所有字符实现假的。这将去的第一个字符串的字符M，以及第二串N个字符，产生一个O（MN）算法中，这是O（N ^ 2）考虑M = C * N，其中c为常数。
希望这有助于。
Hello and thanks for reading. I am working on a homework assignment. I have created a method that compares to strings to see if one is a sub-string of another. I am aware there is already a built in method to do this. The assignment does not allow me to use them. Anyway, the below code is working.
I have to analyze the complexity of the algorithm using Big-O notation. From what I can see the outer loop runs in linear time because it simply runs as many times as the length of the string. Thus: O(n)
The inner loop is different, it may or may not happen, and if it does it may finish before the the length of the second string which is it's input. Thus: O(logn)
So it appears to me the the complexity is O (n*logn). Does this simplify to O(n) or does it stay in its current form? Or am I wrong about the inner loop being 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;
}
}
The inner loop is not logN. Big O measures the worst case complexity. As I understand from your code,the inner loop can run N (length of string 2) times. Explanation follows:
Suppose you have two strings say aaaaaaaa and aaac, the outer loop will match first char, you will go to the inner loop, check every character, then realize a false. Then outer loop will again match the beginning of the 2nd string with second character of first string, then you will again check all characters in second string realize a false. This will go for M characters of the first string, as well as N characters of the second string, yielding a O(MN) algo, which is O(N^2) considering M=c*N where c is a constant.
Hope this helps.
这篇关于子串串算法的大O分析。是否为O（n * LOGN）简化？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
