Python 官方文档:入门教程 => 点击学习
目录计算复杂性算法的复杂性恒定复杂性–O(1)对数复杂性–O(Log N)线性复杂度–O(N)N Log N复杂性–O(N Log N
算法的复杂性是在一个比较的尺度上完成的。以下是不同的类型,从最好到最差。最后,我们还有一个图表,显示它们之间的比较情况。
例如:
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(
到此这篇关于Java如何分析算法的时间和空间复杂度的文章就介绍到这了,更多相关Java空间复杂度内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: Java如何分析算法的时间和空间复杂度
本文链接: https://www.lsjlt.com/news/151799.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0