Java如何分析算法的时间和空间复杂度

目录

• 计算复杂性
• 算法的复杂性
• 恒定复杂性–O（1）
• 对数复杂性–O(Log N)
• 线性复杂度–O（N）
• N Log N复杂性–O（N Log N）
• 多项式复杂性–O（Np）
• Quadratic复杂性–O（N2）
• Cubic复杂性–O（N3）
• 指数复杂性–O（Kn）
• 阶乘复杂性–O（N！）
• 复杂性比较
• 复杂性分析类型
• 最坏情况下的时间复杂度
• 平均案例时间复杂度
• 最佳情况时间复杂度
• 计算复杂性的渐近性
• 渐近分析
• 为什么渐近符号很重要？
• 渐近符号的类型
• Big O Notation – O (G (N))
• Omega Notation – Ω (G (N))
• Θ表示法–Θ（G（N））
• 复杂性类型（基于资源）
• 时间复杂性
• 空间复杂性
• 算术复杂性
• 位复杂性
• Big O Notation – O (G (N))
• 什么是Big O Notation
• 计算Big O时间复杂性

计算复杂性

• 计算复杂性或简单的复杂性是一个计算机科学概念，它关注运行任务所需的计算资源数量。
• 算法复杂性是比较算法效率的一种方法。可以根据程序运行所需的时间（时间复杂度）或消耗的内存量（空间复杂度）来衡量复杂度。

算法的复杂性

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

恒定复杂性–O（1）

• 它规定了O（1）的复杂性。
• 它会经历一个固定数量的步骤，如1、2、3。用于解决给定问题。
• 操作计数与输入数据大小无关。

例如:

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

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

对数复杂性–O(Log N)

• 它的复杂性为O（log（N））。
• 它执行log（N）步骤的顺序。要对N个元素执行运算，通常将对数基数取为2。
• 常数时间算法（渐近）是最快的。对数时间是第二快的。不幸的是，这很难想象。
• 对数时间算法的一个著名示例是二进制搜索算法。

例如：

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）

• 它规定了O（N）的复杂性。
• 如果我们说某物呈线性增长，我们的意思是它的增长与其输入的大小成正比。
• 它包含与在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）

• 它的复杂性为O（n log n）。
• 它是线性+对数复杂性的某种组合。
• 运行时间与输入的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）

• 它规定了O（np）的复杂性。
• 多项式是一个包含二次（n2）、三次（n3）、四次（n4）函数的通用项。

Quadratic复杂性–O（N2）

• 它的复杂性为O（n2）。
• 对于N个输入数据大小，它对N个元素进行N2次运算，以解决给定问题。

Cubic复杂性–O（N3）

• 它的复杂性为O（n3）。
• 对于N个输入数据大小，它对N个元素进行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（kn）。
• 这些增长与输入成指数的某些因子成比例。
• 对于N个元素，它将执行操作的计数顺序，该顺序对输入数据大小具有指数依赖性。

例如，让我们看一个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！）的复杂性。
• 使用蛮力方法解决旅行推销员问题。
• 这类算法的运行时间与输入大小的阶乘成比例。

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

• 与4n2相比，术语5n变得无关紧要
• 在4n2中，4与n2相比变得微不足道
• 当n较大时。函数“ƒ（n）被称为渐近等价于n为n的n2→ ∞“,
• 这里用符号表示为ƒ（n）~ n2或ƒ（n）=n2

为什么渐近符号很重要？

• 它们给出了算法效率的简单特征。
• 它们允许比较各种算法的性能。

渐近符号的类型

• 它曾经编写过运行速度最快、速度最慢的算法。”“最佳情况”和“最坏情况”都是指这样的情况。
• 我们推导了与输入大小有关的复杂性。（以n为例）。
• 这些符号是必不可少的，因为在不增加算法运行成本的情况下，我们可以估计算法的复杂性。
• 渐近表示法是一种比较忽略常数因子和较小输入大小的函数的方法。三种符号用于计算算法的运行时复杂性。
• 渐近表示法是一种比较忽略常数因子和较小输入大小的函数的方法。三个符号计算算法的运行时复杂性。

Big O Notation – O (G (N))

• Big oh是表示算法运行时间上限的形式化方法。
• 这是一个渐近上界。
• f（n）的复杂性表示为O（g（n））。
• 它是对最长时间的度量。

Omega Notation – Ω (G (N))

• Omega是表示算法运行时间下限的形式化方法。
• 这是一个渐近下界。
• f（n）的复杂度表示为Ω（g（n））。
• 它是对最短时间的度量。

Θ表示法–Θ（G（N））

• θ表示法比大oh和ω表示法更精确。如果g（n）既是上界又是下界，则函数f（n）=θ（g（n））。
• 这是一个渐近紧界。
• f（n）的复杂度表示为θ（g（n））。
• 它是对精确时间量的度量。

复杂性类型（基于资源）

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

• 时间复杂性
• 空间复杂性

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

时间复杂性

• 它是衡量算法需要运行的时间量。
• 计算时间复杂性描述了算法运行时的变化，这取决于输入数据大小的变化。
• 换句话说，随着输入数据量（n）的增加，算法退化的程度。

例如：

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

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

给定阵列：

5    3    2    7    9    15

• 如果搜索5，只需执行一次比较，因为它位于零索引中。
• 如果搜索9，则需要执行四次比较，因为它位于第四个索引中。
• 如果您搜索4，则需要执行六次比较，因为您将依次选中每个框，但在其中任何一个框中都找不到它。

在上面的示例中，当您搜索数组中不存在的数字时。在这种情况下，我们必须检查整个阵列，因此，这是最坏情况的一个示例。

在最坏的情况下，线性搜索所需的时间直接取决于输入的大小，因此随着数组大小的增长，所需的时间也会相应增长。

最坏情况为算法提供了一个很好的基准，以比较其解决问题的时间复杂性。

空间复杂性

• 它衡量的是算法运行所需的内存量。
• 空间复杂性包括辅助空间和输入使用的空间。
• 描述根据输入数据的大小，算法需要多少额外内存。

辅助空间是算法使用的额外空间或临时空间。

• 如果我们创建一个大小为n*n的二维数组，我们将需要O（n2）空间。
• 空间复杂性是与时间复杂性并行的概念。如果需要创建大小为n的数组，则需要O（n）空间。如果我们创建一个大小为n*n的二维数组，我们将需要O（n2）空间。
• 在递归调用中，堆栈空间也会计数。

例如：

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表示法的一些亮点：

• Big O与大输入有关。
• Big O表示法是分析和比较算法的框架。
• Big O表示法关心该算法的最坏情况。
• Big O需要降低时间复杂度函数以获得更好的性能。
• 随着输入大小的增长（接近无穷大），CPU必须完成的工作量（时间复杂度）。
• Big O=大阶函数。删除常量和低阶项。E、 g.O（4n2+5n+3）变成O（n2）。
• 计算算法或程序的时间复杂度，这是它使用大O表示法的最常见度量。

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

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

计算Big O时间复杂性

• 要找到算法的Big O，您需要关注其最重要部分的增长。
• 这取决于问题复杂性的大输入值，大值占主导地位，剩余的小值，它们的影响是微不足道的。

例如：

在线性搜索中，算法的时间复杂度为f（n）=2n+3

式中f（n）=2n+3

要解决此问题，请将其分为两部分：

• 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(