函数调用的时间复杂度分析

如果我们把问题再实际化一点，大家能否自己正确的分析出来？

请看下面例子

int n = 100;
for (int i = 0; i < n; i++) {
   function(i);
}

public void function(int num) {
  System.out.println(num);
}

函数体是打印参数，function函数的时间复杂度为O(1)，所以整体的时间复杂度就是循环的次数O(n)。

加入function是下面这样，那又会是什么结果呢？

public void function(int num) {
  for (int i = num; i < n; i++) {
    System.out.println(i);
  }
}

事实上，这和之前我们讲解平方阶时候举得第二个例子是一样的，function内部的循环次数随num的增加（接近n）而减少，所以算法的时间复杂度为O( $n^2$ )

那么接下来大家可以自己联系一下，答案会公布在文章最下方

n++;
function(n);
for (int i = 0; i < n; i++) {
  function(i);
}

for (int i = 0; i < n; i++) {
  for (int j = i; j < n; j++) {
    System.out.println(j);
  }
}

public void function(int num) {
  for (int i = num; i < n; i++) {
    System.out.println(i);
  }
}

常见时间复杂度

例子	时间复杂度	装逼术语
$5201314$	O( $1$ )	常数阶
$3n+4$	O( $n$ )	线性阶
$3n^2+4n+5$	O( $n^2$ )	平方阶
$3log_2n+4$	O( $log_2n$ )	对数阶
$2n+3nlog_2n+14$	O( $nlogn$ )	nlogn阶
$n^3+3n^2+4n+6$	O( $n^3$ )	立方阶
$2^n$	O( $2^n$ )	指数阶

常用的时间复杂度所耗费的时间从小到大依次是

$O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$

最坏情况与平均情况

从心理学角度来说，每个人对将要发生的事情都会有一个预期，比如看到半杯水，有的人会说：“哇，还有半杯水呢”，但是有的人就会说：“我的天，只剩半杯水了”

一般人常出于一种对未来失败的担忧，所有预期的时候会做出最坏的打算。这样，即使最糟糕的结果出现，当事人也有了心理准备，比较容易接受结果，加入结果并非最坏的状况，这会使人更加快乐，瞧，事情发展的还不错嘛！

算法的分析也是类似，我们在一个具有n个随机数的数组中查找某个数字，最好的情况是第一次就找到了，那么算法的时间复杂度为O(1)，但是也有可能全都找了一遍，最后一个才是，那么时间复杂度为O(n)。

平均运行时间是期望的运行时间

最坏运行时间是一种保证，在应用中，这是一种最重要的需求，通常除非特别指定，我们提到的运行时间就是最坏情况的运行时间

算法的空间复杂度

我们写代码时，完全可以用空间来换取时间

举个例子来说，要判断某年是否为闰年

方法一：你可以花一点心思来写一个算法，每给一个年份，就可以通过这个算法计算判断传入年份是否为闰年。

方法二：事先建立一个有2050个元素的数组，然后把所有的年份按下标的数字进行对应，如果是闰年，则此数组元素的值为1，如果不是元素值为0，这样，所谓判断某一年是否为闰年就变成了查找这个数组对应下标的值得问题。

第一种方法相比第二种来说明显的节省空间，但是每一次判断是否为闰年都需要经过一系列的计算才能知道，第二种方法虽然需要在内存中存储很多元素，但是每次查询的时候只是需要通过索引获取值。

这就是一种使用空间上的开销来换取计算时间开销的小技巧，到底哪一种方法好，其实还是要看用在什么地方，这里只是一个例子，误杠！！！

算法的空间复杂度通过计算算法所需的存储空间实现，算法的空间复杂度的计算公式记作：

$S(n) = O(f(n))$

其中， $n$ 为问题的规模， $f(n)$ 为语句关于n所占存储空间的函数

一般情况下，一个程序在机器上执行时，除了需要存储程序本身的指令、常数、变量和输入数据外，还需要存储对数据操作的存储单元，若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。

通常我们都是用“时间复杂度”来指运行时间的需求，使用“空间复杂度”指空间需求

练习答案

n++;                                    // 1
function(n);                            // n
for (int i = 0; i < n; i++) {           // n^2
  function(i);                        
}

for (int i = 0; i < n; i++) {           // n^2
  for (int j = i; j < n; j++) {
    System.out.println(j);
  }
}

public void function(int num) {
  for (int i = num; i < n; i++) {
    System.out.println(i);
  }
}

$1 + n + n^2 + n^2 = 2n^2+n+1$
根据前面总结的三点，去掉常数、保留最高次项、去掉最高次项系数，则最终结果为O( $n^2$ )

内容均来源于学习资料，在学习过程中进行记录，如有侵权联系作者进行删除

Change the world by program

05.时间复杂度和空间复杂度-03