亲宝软件园·资讯

展开

Java空间复杂度

 sofia   人气:0

计算复杂性

算法的复杂性

算法的复杂性是在一个比较的尺度上完成的。以下是不同的类型,从最好到最差。最后,我们还有一个图表,显示它们之间的比较情况。

恒定复杂性–O(1)

例如:

int n = 10;
System.out.println("value of n is : " + n);

在上面的示例中,它不依赖于n的值&总是需要一个常量/相同的运行时间。

对数复杂性–O(Log 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。

线性复杂度–O(N)

例如:

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的值运行循环。

N Log N复杂性–O(N Log 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

多项式复杂性–O(Np)

Quadratic复杂性–O(N2)

Cubic复杂性–O(N3)

等等…

例如:

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(Kn)

例如,让我们看一个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!)

例如,让我们看一个简单的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

为什么渐近符号很重要?

渐近符号的类型

Big O Notation – O (G (N))

Omega Notation – Ω (G (N))

Θ表示法–Θ(G(N))

复杂性类型(基于资源)

根据资源,我们可以将其分为两种类型,

我们将关注时间和空间的复杂性。简言之,我们将讨论更多类型的复杂性。

时间复杂性

例如:

我们将用最坏的情况来衡量时间复杂性。

线性搜索,我们需要检查每个索引,直到得到所需的结果。让我们假设下面就是这个数组。

给定阵列:

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变量的值是反复存储和,因此空间复杂度是恒定的。

其他一些类型的复杂性

算术复杂性

位复杂性

Big O Notation – O (G (N))

大O表示法用于表示关于输入大小增长的算法复杂性。因此,它根据算法在大输入情况下的性能对算法进行排序。

什么是Big O Notation

关于Big O notation的要点:

以下是关于大O表示法的一些亮点:

当我们可以从几种不同的方法中选择解决问题时,复杂性通常会随着输入的大小而变化。大O表示法允许我们轻松地将一种算法与另一种算法进行比较,以帮助我们选择最佳选项。

例如,如果您有一个将数组作为输入的函数,如果您增加集合中的元素数,您仍然会执行相同的操作;您有一个恒定的运行时。另一方面,如果CPU的工作与输入数组的大小成比例增长,则有一个线性运行时O(n)。

计算Big O时间复杂性

例如:

在线性搜索中,算法的时间复杂度为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(

加载全部内容

相关教程
猜你喜欢
用户评论