計算算法的最壞情況下運行時間複雜度

-1

我正在嘗試計算我創建的算法的最壞情況運行時複雜度，該算法檢查給定的字符串是否爲字符串列表的封面字符串（對於每個字符串在列表中包含每個字符串中的字符，保持從左到右的順序）。計算算法的最壞情況下運行時間複雜度

我現在認爲這個算法的最壞情況運行時間複雜度是O（N^2）嗎？我的邏輯是對於執行n次的內部for循環，調用複雜度爲O（1）的if語句。並且外循環也被執行n次，導致n * n或O（n^2）的t（n）。

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")); 
} 

}

來源

2015-12-02 Mickd94

這段代碼非常令人困惑，因爲你正在變異'stringList' - 它也是'list'，因爲你如何從'main'調用它 - 然後遍歷'list'。你爲什麼要在'isCover'中改變'stringList'？ –

當您嘗試確定複雜性時，您必須尋找隱藏的循環 - 考慮如何實現indexOf。 –

@AndyTurner現在知道調用indexOf函數實際上不是一個固定的時間複雜度，並且應該具有複雜度O（n * m），在這個例子中m總是1，因爲我正在尋找字符，案件的複雜性實際上更接近O（n^3）？ – Mickd94

的的indexOf的Java的implementation的複雜度爲O（M * n），其中n和m分別是搜索字符串和模式的長度。當N = stringList.size（），M = stringList.get（...）.length（）和C = cover.length（）時，最壞情況下的複雜度爲O（N * M * C）。

來源

2015-12-02 23:20:04

感謝您的評論和信息，那麼我會假設O（N * M * C）等於O（N^3）嗎？並且indexOf函數的複雜性將會是O（n），因爲我正在尋找字符時，我所查找的模式的長度始終爲1。 – Mickd94

這取決於你的數量。如果我們在stringList（f（sum_chars_of_stringList））和cover.length = const的所有字符串中都講述了彙總字符串的函數，那麼它就是O（N）。如果你說我在列表中有N個元素，封面上有N個元素，列表中每個字符串都有N個元素 - >它是O（N^3）。首先，你需要不需要的東西和你使用的東西。 –

計算算法的最壞情況下運行時間複雜度

回答

相關問題