在本文中，我们将讨论一个复杂且可怕的主题，即计算算法的运行时间和空间复杂度。大多数程序员在面试中对于算法都觉得比较困难。

这篇文章将尽量的减少理论部分，并通过图表和示例进行了更简单的解释，相信在阅读本文后会轻松理解时间/空间复杂性。

大(O) 表示法

大 O 表示法是一种数学表示法，描述函数在参数趋于特定值或无穷大时的极限行为。

我们使用 Big O 表示法来描述给定算法的性能。通过该符号，我们可以发现特定算法是否可以随着输入的增加而扩展。

让我们看看如何计算算法的 Big 0 表示法

基本上，这种渐近符号用于从理论上测量和比较算法的最坏情况。对于任何算法，只要我们正确识别依赖于输入大小 n 的操作，Big-O 分析就应该很简单。我们必须消除所有恒定因素。

算法的运行时分析

一般情况下，我们主要通过衡量和比较算法最坏情况下的理论运行时间复杂度来进行性能分析。

时间复杂度的类型

1. O(1)——恒定时间

任何算法的最快运行时间都是 O(1)，通常称为恒定运行时间。在这种情况下，无论输入大小如何，算法总是花费相同的时间来执行。这是算法的理想运行时间，但很难实现。

在下面的代码中，我们打印数字数组的第一个元素，输入的大小并不重要。因此，我们将其视为常数时间并表示为 O(1)。

public void print(int[] numbers){
  System.out.println(numbers[0]);
}

在下面的代码中，我们添加了 2 行，执行 3 行的时间复杂度变为 O(3)。但它是否可以忽略不计，我们将其简化为 O(1)，这意味着恒定时间，即无论输入大小如何，算法的运行时间始终相同？

public void print(int[] numbers){
  System.out.println(numbers[0]);
  System.out.println(numbers[1]);
  System.out.println(numbers[2]);
}

在实时情况下，算法的性能（运行时）取决于 n，即输入的大小或每个输入项所需的操作数。因此，大多数情况下我们不会遇到在恒定时间内运行的算法。

2. O(n)——线性时间

在此算法中，运行时间与输入大小 n 成正比。

在下面的代码中，循环运行了n次。如果n为1，则该语句打印一次，如果n为1000，则将打印1000个元素。因此时间复杂度与输入大小直接相关线性增长

public void print(int[] numbers){
  for(int i = 0; i < numbers.length; i++){
    System.out.println(numbers[i]);
  }  
}

假设我们在循环之前和之后添加了 2 个打印语句。这里时间复杂度变为 O(1+ n + 1) => O(n + 2)。

常数可以忽略不计，因为它不会显著影响算法的性能，因此我们将其简化为 O(n)

public void print(int[] numbers){
  System.out.println("before the loop");
  for(int i = 0; i < numbers.length; i++){
    System.out.println(numbers[i]);
  }  
  System.out.println("after the loop");
}

下面让我们看另一个例子。这里的时间复杂度是 O(n) + O(n) => O(2n)。我们再次简化为 O(n)，因为该算法仍然是线性的。

public void print(int[] numbers){
 for(int i = 0; i < numbers.length; i++){
    System.out.println(numbers[i]);
  }  
 for(int i = 0; i < numbers.length; i++){
    System.out.println(numbers[i]);
  } 
}

3. O(n2) — 二次方复杂度

该算法是多项式算法的一种，其中计算步骤的数量随着变量数量的幂而增长。

让我们考虑下面的代码。这里我们嵌套了 for 循环。对于 n 的输入大小，算法运行 n2 次。如果数字数组的大小为 10，则此代码将运行 100 次，并且循环内有循环的效率非常低

public void print(int[] numbers){
  for(int first: numbers){
    for(int first: numbers){
     System.out.println(first + " " + second);
    }
  }
}

让我们在下面添加另一个循环。现在算法的时间复杂度变为O(n+n2)。由于 Big O 表示法测量的是近似时间而不是精确时间，因此我们将时间复杂度简化为 O(n2)。

public void print(int[] numbers){
   for(int first: numbers){
     System.out.println(first + " " + second);
    }
  
   for(int first: numbers){
    for(int first: numbers){
     System.out.println(first + " " + second);
    }
  }
}

如果前面的例子中有 3 个嵌套循环，那么时间复杂度就会增加到 O(n3)。 O(n3) 的效率低于 O(n2)。

4. O(logn)——对数复杂度

与 n 成对数比例增长的算法。如下所示，对数算法在一定时间后变得高效，并且比线性算法更快。

让我们思考下图，其中以图显示了二分搜索和线性搜索算法。需要注意的重要一点是，二分搜索仅适用于已排序的数组。

在线性搜索的情况下，会在找到 9 之前检查每个元素。时间复杂度是 O(n)

在二分搜索的情况下，数组始终分为 2 个部分，代码会查找该分区。我们将搜索范围缩小了一半。这是对数时间复杂度

假设数组中有 100 万个已排序的数据，我们想要找到最后一个元素。在最坏的情况下，我们可以在 19 次比较中找到该元素，而 O(n) 需要 100 万次比较。现在您可以比较 O(log n) 与 O(n) 的效率如何

在任何算法中，如果我们将工作量减少一半，那么它就是 O(log n)。树和图的数据结构就属于这一类。

5. O(nlogn) — 对数线性算法

O(nlogn) 称为对数线性复杂度。O(n logn) 意味着 logn 操作将发生 n 次。O(n logn) 时间在递归排序算法、使用二叉树排序的排序算法以及大多数其他类型的排序中很常见

此时间复杂度类似于 O(log n)，但它在时间复杂度为 O(n) 的循环内执行。

如上所述，在任何算法中，如果我们将工作量减少一半，那么它的复杂度就是 O(logn)。我们看到了二分搜索的例子，它只进行搜索，因此时间复杂度是 O(n)。但考虑像归并排序这样的排序算法的情况，它需要将项目分成一半 O(n) 并需要在循环中将它们合并回来，即 O(n)。现在时间复杂度变成了O(nlogn)

下图说明了合并排序的步骤。该代码遍历整个项目，然后在循环内执行排序操作。

反复将一组数据分成两半，然后使用时间复杂度为 O(n) 的子算法独立处理这些两半的算法，其总体时间复杂度将为 O(nlogn)。

O(nlogn) 比 O(n2) 更好、更高效。归并排序、快速排序和堆排序等高效排序算法的复杂度为 O(nlogn)，而冒泡排序、插入排序和选择排序等低效排序算法的复杂度为 O(n2)

6. O(2^n) — 指数复杂度

指数增长与对数增长相反。在一定数量的输入后，对数增长变得有效，但随着输入大小的增长，指数增长变得更慢且效率低下

让我们看看以下使用递归计算斐波那契数列的方法示例。

class fibonacci
{
 static int fib(int n)
 {
    if (n <= 1)
     return n;
   return fib(n-1) + fib(n-2);
 }
public static void main (String args[])
 {
  int n = 9;
  System.out.println(fib(n));
 }
}

正如您所看到的，每个函数都调用另外两个函数，因此它呈指数增长。想象一下，你使用这个算法来找到 100,000 个项目的斐波那契数，机器会发疯。 所以这是指数时间复杂度 O(2^n) 并且完全不可扩展且效率低下

7.阶乘算法——O(n!)

以 O(n!) 运行的示例算法是

• 字符串的排列。
• 通过暴力搜索解决旅行推销员问题

让我们考虑一下计算字符串排列的程序。对于输入大小 5，它执行 120 次操作，即 5！

getPermutations('ab') // ab, ba... 
// n = 2, f(n) = 2; 
getPermutations('abc') // abc, acb, bac, bca, cab, cba... 
// n = 3, f(n) = 6; 
getPermutations('abcd') // abcd, abdc, acbd, acdb, adbc, adcb, bacd... 
// n = 4, f(n) = 24; 
getPermutations('abcde') // abcde, abced, abdce, abdec, abecd, abedc, acbde... 
// n = 5, f(n) = 120;

因此，该算法的时间复杂度低于 O(n!)，这是性能最差的时间复杂度，如下所示

下图显示了我们讨论的所有 7 种时间复杂度类型的摘要，您可以清楚地看到它们属于哪一类。

改进低效算法

如果您的算法属于“糟糕”和“糟糕”的类别，您可以通过采用动态规划编程等技术来提高它们的效率。如果您想了解更多信息，请搜索动态规划。

在前面的示例中，我们已经看到每次都会计算子集，因此时间复杂度增长到 O(2^n) 或 O(n!)。

动态规划主要是对普通递归的优化。无论何时我们看到重复调用相同输入的递归解决方案，我们都可以使用动态规划对其进行优化。这个想法是简单地存储子问题的结果，这样我们就不必在以后需要时重新计算它们。这种简单的优化将时间复杂度从指数降低到多项式。这样就可以提高CPU的效率

空间复杂度

算法或计算机程序的空间复杂度是解决计算问题实例所需的存储空间量，作为输入特征的函数。它是算法完全执行之前所需的内存。

时间和空间复杂度是两个不同的极点。在大多数情况下，当您为算法提供更多内存时，它可以运行得更快，因此我们可以以额外内存为代价实现更高的效率，这是一个可以忽略不计的成本

除了输入大小之外，我们总是计算程序所需的额外内存的空间复杂度。

在下面的示例中，我们接收一个数字数组并打印它。在这里，内存的大小并不重要。我们需要计算的是循环变量 i 的大小，它可以忽略不计。因此这里的空间复杂度是O(1)

public void print(int[] numbers){
  for(int i = 0; i < numbers.length; i++){
    System.out.println(numbers[i]);
  }  
}

让我们考虑以下场景。这里我们声明了一个新数组并分配了与输入内存等效的内存。

因此空间复杂度变为 O(n + 1) => O(n)

public void print(int[] numbers){
  
  Integer[] copy = new Integer[numbers.length]
  for(int i = 0; i < numbers.length; i++){
    System.out.println(numbers[i]);
  }  
}

当我们编程时，我们肯定需要优化空间，尤其是像 Java 这样的编程语言。类变量或引用也存储在堆中。还会在堆中创建ArrayList对象或LinkedList对象

如果我们不优化空间，那么JVM 堆大小很快就会被填满，从而导致内存不足的错误。