Big O
Ex. 1 Suppose we had an algorithm that took in an array of strings,sorted each string,and then sorted the full?array. What would the runtime be? 假设我们有一个算法把一个String数组,对其中每个字符串的字符排序,并对整个数组排序。时间复杂度会是多少? ? 很多人会这样推理:对一个String所有字符排序是O(N log N),并且我们对每个字符串都这么操作,所以复杂度是?O(N*N log N)。 我们还要对数组里的String进行排序,所以额外加上O( N log N)。 所以总的运行时间是O(N2?log N + N log N),也就是 O(N2?log N)。 我们来这么定义: ? 用s来表示最长字符串的长度 综上,总的复杂度为?O(a*s(log a + log s) ? Ex.2 This code counts all permutations of a string. 1 void permutation(String str) { 2 permutation(str,""); 3 } 4 5 void permutation(String str,String prefix) { 6 if (str.length() == 0) { 7 System.out.println(prefix); 8 } else { 9 for (int i = 0; i < str.length(); i++) { 10 String rem = str.substring(0,i) + str.substring ( i + 1); 11 permutation(rem,prefix + str.charAt(i); 12 } 13 } 14 } 如果一个String里有7个字符, 第一次我们有7个选择,下一次我们有6个,以此类推。因此总选择数是7 * 6 * 5 * 4 * 3 * 2 * 1, 也就是7! (7 factorial). 由此得知总共有n!种排列。 由于String的长度为n,所以总的排列数不会超过n * n!(可能存在相同字符)。 那每次调用permutation这个方程会花多久。 执行line 7会花O(n)的时间因为每个字符都会被打印。 执行line 10 和 11会花O(n)的时间(substring)。 所以总复杂度为O(n2 * n!)。 ? Ex.3 下面是两个输出斐波那契数列的代码: 1 void allFib(int n) { 2 for (int i = 0; i < n; i++) { 3 System.out.println(i + ": " + fib(i)); 4 } 5 } 6 7 int fib(int n) { 8 if (n <= 0) return 0; 9 else if (n == 1) return 1; 10 return fib(n - 1) + fib(n - 2); 11 } 很容易我们能得出复杂度为O(2n)。 1 void allFib(int n) { 2 int[] memo = new int[n + 1]; 3 for (int i = 0; i < n; i++) { 4 System.out.println(i + ": " + fib(i,memo)); 5 } 6 } 7 8 int fib(int n,int[] memo) { 9 if (n <= 0) return 0; 10 else if (n == 1) return 1; 11 else if (memo[n] ) > 0) return memo[n]; 12 13 memo[n] = fib(n - 1,memo) + fib(n - 2,memo); 14 return memo[n]; 15 } ? 那第二个代码的复杂度是多少呢? 这里是典型的空间换时间,由于每次调用的时候传入了memo数组,所以在计算之前的fib[]时我们可以直接赋值,因此复杂度为O(n) ? Ex.4 The following code prints all strings of length k where the characters are in sorted order. It?does this by generating all strings of length k and then checking if each is sorted. What is its?runtime? 以下代码输出了所有字符已排序的k长度的String。复杂度是? 1 int numChars = 26; 2 void printSortedStrings(int remaining) { 3 printSortedStrings(remaining,""); 4 } 5 void printSortedStrings(int remaining,String prefix) { 6 if (remaining == 0) { 7 if (isInOrder(prefix) { 8 system.out.println(prefix); 9 } 10 } else { 11 for (int i = 0; i < numChars ; i++) { 12 char c = ithLetter(i); 13 printSortedStrings(remaining - 1,prefix + c); 14 } 15 } 16 } 17 boolean islnOrder(String s) { 18 for (int i = 1; i < s.length(); i++) { 19 int prev ithLetter(s.charAt(i - 1)); 20 int curr = ithLetter(s.charAt(i)); 21 if (prev > curr) { 22 return false; 23 } 24 } 25 return true; 26 } 27 char ithLetter(int i) { 28 return (char) ( (int) ‘a‘) + i); 29 } 复杂度是O(kck)。 k是String的长度,c是英文字母的数量。 这个代码用O(ck)。 检查排序要花O(k)的时间。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |