Расчет наихудшей сложности времени выполнения алгоритма

Question

Я пытаюсь решить сложность времени наихудшего случая для созданного мной алгоритма, который проверяет, является ли данная строка строкой обложки для списка строк (для каждой строки в списке, содержит в себе все строковые символы, сохраняя порядок слева направо).

Был ли я прав в настоящее время, полагая, что сложность времени выполнения в худшем случае для этого алгоритма равна O (N^2)? Моя логика заключается в том, что для внутреннего цикла for, который выполняется n раз, вызывается оператор if со сложностью O (1). И внешний цикл выполняется также n раз, что приводит к t (n) n * n или O (n^2).

public class StringProcessing { 

//ArrayList created and 3 fields added. 
public static ArrayList<String> stringList = new ArrayList<>(); 
public static String list1 = "abc"; 
public static String list2 = "def"; 
//public static String list3 = "fad"; 
//public static String list4 = "monkey"; 
//public static String list5 = "def"; 

//Boolean method to test whether a given string is a cover string for a single string. 
//Method contains a for-each loop to iterate through characters of test String s. 
public static boolean isSingleCover(String s, String cover) 
{  
    int i = 0; 
    for(char c : s.toCharArray()) 
     if((i = cover.indexOf(c, i)) == -1) 
      return false; 
    return true; 
} 

//Second Boolean method to test whether a given string is a cover string for a given list of strings. 
//The algorithm includes reference to the previous method for testing a single String, and uses this method 
//for each string in the ArrayList. 
public static boolean isCover(ArrayList<String> list, String cover) 
{ 
    stringList.add(list1); 
    stringList.add(list2); 
    //stringList.add(list3); 
    //stringList.add(list4); 
    //stringList.add(list5); 
    for(String s : list) 
     if(!isSingleCover(s, cover)) 
      return false; 
    return true; 
} 

public static void main(String[] args) { 
    System.out.println(StringProcessing4.isCover(stringList, "adftyhgusbgusibadsjfksvgjchjgdkepf")); 
} 

} 

Answer 1

Сложность в Java implementation из IndexOf представляет собой О (т * п), где п и т являются длина строки поиска и рисунка соответственно.

Такая наихудшая сложность O (N * M * C), когда N = stringList.size(), M = stringList.get (...). Length() и C = cover.length()