算法的复杂性是在一个比较的尺度上完成的。以下是不同的类型,从最好到最差。最后,我们还有一个图表,显示它们之间的比较情况。
例如:
int n = 10; System.out.println("value of n is : " + n);
在上面的示例中,它不依赖于n的值&总是需要一个常量/相同的运行时间。
例如:
for (int i = 1; i < n; i = i * 2){ System.out.println("value of i is : " + i); }
如果n为4,则输出如下:
value of i is : 1
value of i is : 2
在上述示例中,复杂性为log(4)=2。
例如:
for (int i = 0; i < n; i++) { System.out.println("value of i is : " + i); }
如果n为4,则输出如下:
value of i is : 0
value of i is : 1
value of i is : 2
value of i is : 3
在上述示例中,复杂性为O(4)=4。
它取决于n的值,它总是为n的值运行循环。
例如:
for (int i = 1; i <= n; i++){ for(int j = 1; j < n; j = j * 2) { System.out.println("value of i : " + i + " and j : " + j); } }
If n is 4, the output will be the following:
value of i : 1 and j : 1
value of i : 1 and j : 2
value of i : 2 and j : 1
value of i : 2 and j : 2
value of i : 3 and j : 1
value of i : 3 and j : 2
value of i : 4 and j : 1
value of i : 4 and j : 2
在上述示例中,复杂性为
O(4) = 4 * log(4) = 4 * 2 = 8
等等…
例如:
for (int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { System.out.println("value of i : " + i + " and j : " + j); } }
如果n为4,则输出如下:
value of i : 1 and j : 1
value of i : 1 and j : 2
value of i : 1 and j : 3
value of i : 1 and j : 4
value of i : 2 and j : 1
value of i : 2 and j : 2
value of i : 2 and j : 3
value of i : 2 and j : 4
value of i : 3 and j : 1
value of i : 3 and j : 2
value of i : 3 and j : 3
value of i : 3 and j : 4
value of i : 4 and j : 1
value of i : 4 and j : 2
value of i : 4 and j : 3
value of i : 4 and j : 4
此算法将运行42=16次。注意,如果我们要嵌套另一个for循环,这将成为一个O(n2)算法。
在上述示例中,复杂性为O(n2)=16。
例如,让我们看一个O(2n)时间算法的简单示例:
for (int i = 1; i <= Math.pow(2, n); i++){ System.out.println("value of i is : " + i); }
如果n为4,则此示例将运行24=16次。
例如,让我们看一个简单的O(n!)时间算法:
for (int i = 1; i <= factorial(n); i++){ System.out.println("value of i is : " + i); }
如果n为4,则此算法将运行4!=24次。
以下是所述时间复杂性的图表。X轴是元素的数量,Y轴是在各种复杂度下所需的时间。正如你所看到的,O(1)和O(logN)几乎没有变化,但2^n和n!就像刺穿天空。
渐近曲线和直线是那些更接近但不相交的曲线和直线。
例如:
function ƒ (n) = 4n2+5n
根据资源,我们可以将其分为两种类型,
我们将关注时间和空间的复杂性。简言之,我们将讨论更多类型的复杂性。
例如:
我们将用最坏的情况来衡量时间复杂性。
线性搜索,我们需要检查每个索引,直到得到所需的结果。让我们假设下面就是这个数组。
给定阵列:
5 3 2 7 9 15
在上面的示例中,当您搜索数组中不存在的数字时。在这种情况下,我们必须检查整个阵列,因此,这是最坏情况的一个示例。
在最坏的情况下,线性搜索所需的时间直接取决于输入的大小,因此随着数组大小的增长,所需的时间也会相应增长。
最坏情况为算法提供了一个很好的基准,以比较其解决问题的时间复杂性。
辅助空间是算法使用的额外空间或临时空间。
例如:
int total = 0; int n = 5; for (int i = 1; i <= n; i++){ total += i; } System.out.println("n value is : " + n); System.out.println("total value is : " + total);
在上面的示例中,total变量的值是反复存储和,因此空间复杂度是恒定的。
其他一些类型的复杂性
大O表示法用于表示关于输入大小增长的算法复杂性。因此,它根据算法在大输入情况下的性能对算法进行排序。
关于Big O notation的要点:
以下是关于大O表示法的一些亮点:
当我们可以从几种不同的方法中选择解决问题时,复杂性通常会随着输入的大小而变化。大O表示法允许我们轻松地将一种算法与另一种算法进行比较,以帮助我们选择最佳选项。
例如,如果您有一个将数组作为输入的函数,如果您增加集合中的元素数,您仍然会执行相同的操作;您有一个恒定的运行时。另一方面,如果CPU的工作与输入数组的大小成比例增长,则有一个线性运行时O(n)。
例如:
在线性搜索中,算法的时间复杂度为f(n)=2n+3
式中f(n)=2n+3
要解决此问题,请将其分为两部分:
在第一部分中,有2n,这一循环最多重复n次,所以将大值视为n,所以考虑n值,
&在第二部分中,我们有一个常量值3,与n的数量级相比,它是微不足道的,因此可以忽略该常量值。
Big O表示法关心最坏的情况。
线性搜索是一种算法,Big O表示为,O(n)。
Java集合框架的时空复杂性:
Below are the Big O performance of common functions of different Java Collections. List | Add | Remove | Get | Contains | Next | Data Structure ---------------------|------|--------|------|----------|------|--------------- ArrayList | O(1) | O(n) | O(1) | O(n) | O(1) | Array LinkedList | O(1) | O(1) | O(n) | O(n) | O(1) | Linked List CopyOnWriteArrayList | O(n) | O(n) | O(1) | O(n) | O(1) | Array Set | Add | Remove | Contains | Next | Size | Data Structure ----------------------|----------|----------|----------|----------|------|------------------------- HashSet | O(1) | O(1) | O(1) | O(h/n) | O(1) | Hash Table LinkedHashSet | O(1) | O(1) | O(1) | O(1) | O(1) | Hash Table + Linked List EnumSet | O(1) | O(1) | O(1) | O(1) | O(1) | Bit Vector TreeSet | O(log n) | O(log n) | O(log n) | O(log n) | O(1) | Red-black tree CopyOnWriteArraySet | O(n) | O(n) | O(n) | O(1) | O(1) | Array ConcurrentSkipListSet | O(log n) | O(log n) | O(log n) | O(1) | O(n) | Skip List Queue | Offer | Peak | Poll | Remove | Size | Data Structure ------------------------|----------|------|----------|--------|------|--------------- PriorityQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap LinkedList | O(1) | O(1) | O(1) | O(1) | O(1) | Array ArrayDequeue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List ConcurrentLinkedQueue | O(1) | O(1) | O(1) | O(n) | O(n) | Linked List ArrayBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Array PriorirityBlockingQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap SynchronousQueue | O(1) | O(1) | O(1) | O(n) | O(1) | None! DelayQueue | O(log n) | O(1) | O(log n) | O(n) | O(1) | Priority Heap LinkedBlockingQueue | O(1) | O(1) | O(1) | O(n) | O(1) | Linked List Map | Get | ContainsKey | Next | Data Structure ----------------------|----------|-------------|----------|------------------------- HashMap | O(1) | O(1) | O(h / n) | Hash Table LinkedHashMap | O(1) | O(1) | O(1) | Hash Table + Linked List IdentityHashMap | O(1) | O(1) | O(h / n) | Array WeakHashMap | O(1) | O(1) | O(h / n) | Hash Table EnumMap | O(1) | O(1) | O(1) | Array TreeMap | O(log n) | O(log n) | O(log n) | Red-black tree ConcurrentHashMap | O(1) | O(1) | O(h / n) | Hash Tables ConcurrentSkipListMap | O(log n) | O(log n) | O(