当前位置：移动技术网 > IT编程>开发语言>Java > 算法-复杂度

算法-复杂度

2020年07月16日 | 移动技术网IT编程 | 我要评论

1. 什么是时间复杂度？

what is Time Complexity？

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数->进而分析T(n)随n的变化情况并确定T(n)的数量级
它表示随问题规模n的增大，算法执行时间的增长率是->f(n)就简称为时间复杂度 记作 $O(f(n))$

先简单的介绍 $O(1) \space O(n)\space O(n^2)$ , 官方名称常数阶，线性阶，平方阶

那么我们怎么去计算时间复杂度呢？这个算法执行时间的增长率是啥东东

推导大O阶：

用常数1取代运行时间中的所有加法常数

在修改后的运行次数函数中，只保留最高阶项

如果最高阶项存在而且不是1，则去除与这个项相乘的常数。结果就是大O阶

说实话这三行文字看起比较抽象，有点类似高数里面的求导？

1.1 常数阶

对于顺序结构的时间复杂度，下面这高斯算法，时间复杂度是 $O(1)$ 。

private static void gaussian(){
       Clock clock = Clock.systemUTC();
       System.out.println(clock.millis());	// 测试Java8提供的新方法
       long startTime=System.currentTimeMillis();   // 获取开始时间
       System.out.println(startTime);
       // 对于顺序结构的时间复杂度 跟n的大小无关 O(1)
       int sum, n=1000000;
       sum = (n+1)*n/2;
       System.out.println(sum);
       long endTime=System.currentTimeMillis(); // 获取结束时间
       System.out.println("程序运行时间： "+(endTime-startTime)+"ms");
   }

另外对于分支结构(不包含在循环结构中)而言，无论是false还是true，执行次数是恒定的，不会随着n的变化而变化

1.2 线性阶

线性阶的循环结构会稍微复杂一点，要确定算法程序的阶次，通常我们需要对某个确定的语句或者某个语句集代码块的运行次数，分析复杂度，关键分析循环结构的运行情况

private static void myLoop(){
       int n = 10000;
       for (int i = 0; i < n; i++) {
           // todoSomething
           System.out.println(i);
       }
   }

这个在循环体里面的代码块必须执行n次，所以时间复杂度是 $O(n)$

1.3 对数阶

private static void logarithm(){
       int n = 10000, i=0;
       // i的每次变化阶级影响着循环的次数 所以需要根据公式计算而不是O(n)
       while(i < n){
           i = i*2;
       }
   }

由于i每次乘以2，有公式 $2^x=n$ ,计算得出： $x=log_2n$ ,所以这个循环的时间复杂度是 $log_2{n}$ ,也就是 $O(log_2{n})$

1.4 平方阶

private static void mySquare(){
    int n = 100;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.print(i + j);
        }
        System.out.println();
    }
}

这是一个循环嵌套，内层循环是 $O(n)$ ,对于外层循环而言也是 $O(n)$ ；所以整个循环体时间复杂度是 $O(n^2)$
如果外层循环改为m，时间复杂度就变为 $O(mn)$
那么下面这个例子时间复杂度是多少呢？

private static void mySpecialSquare(){
   int n = 100;
   for (int i = 0; i < n; i++) {
   		// 这里j每次从i开始了 不是每次从0开始
       for (int j = i; j < n; j++) {
       		// 这里要求是O(1)的操作
           System.out.print(i + j);
       }
       System.out.println();
   }
}

这时候就不能单独分析内层和外层了，因为内层循环受到外层循环的条件i的影响；所以整体分析了：
当 $0\le i<n$ ,计算出内循环总的执行次数：
$\color{blue} \displaystyle\sum_{i=1}^n i=1+2+3+...+(n-1)+n=\frac {n(n+1)} 2=\frac {n^2} 2 +\frac n 2$
随着你的增大，只保留我们的最高项，然后去除系数，就得到 $O(n^2)$

好了经过徐师兄上面例子的前奏预热，下面摆几个姿势练练技术

int n,i,j;
function(n);// O(n)
for(i=0; i<n; i++){// O(n^2)
	function(n);
}
forfor(i=0; i<n; i++){// n(n+1)/2
	for (int j = i; j < n; j++) {
		// 执行O(1)操作
	}
}

这个其实就是把前面几种情形通过顺序结构连接起来而已，所以总的执行次数是：
$\color{green}f(n)=1+n+n^2+\frac {n(n+1)} 2=\frac 32 n^2 + \frac32n+1$
随着n的增大，这个代码的时间复杂度最终也是 $O(n^2)$

1.5 常见的时间复杂度

程序执行次数	时间复杂度O	非正式术语
12常数	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2+2n+1$	$O(n^2)$	平方阶
$log_2n$	$O(logn)$	对数阶
$3n+2nlog_2n+1$	$O(nlogn)$	$nlogn$ 阶
$4n^3+3n^2+2n+1$	$O(n^3)$	立方阶
$2^n$	$O(2^n)$	指数阶

它们的大小关系是(高中是不是证明过很多次了？(^^))：
$\color{red}O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$
像 $O(n^3)$ 及以上的时间复杂度过大，基本不会去考虑采用这个算法

1.6 最坏情况与平均情况

最坏情况运行时间：这是最重要的指标，一般在没有特殊指定下都是指最坏时间复杂度
平均运行时间：通过运行一定数量的实验数据得到的是实际情况最有意义的

2. 什么是算法空间复杂度

通常我们在写代码的时候，完全可以用空间来换取时间，定义：计算算法所需的存储空间。
通常“复杂度”都只时间复杂度，也是研究的重点

总结：算法的优劣度直接决定了程序运行的效率
愚公移山的精神固然值得学习，但是发明炸药和挖掘机是更加聪明的做法

本文地址：https://blog.csdn.net/blackxc/article/details/107347312

您可能感兴趣的文章:

如对本文有疑问，点击进行留言回复！！

rfid档案管理-基于RFID技术在智能档案柜管理中的应用—铨顺宏

基于RFID技术在智能档案柜管理中的应用1.行业现状随着企事业单位的发展，各种信息档案资料数量逐日增多，档案的种... [阅读全文]
java-jar 参数

-Xmx : 指定堆的最大大小-Xms : 设置堆的最小和初始大小-XX:+UseG1GC : 使用G1收集器-... [阅读全文]
easyexcel阿里java开源框架,导入excel数据

在项目实际开发过程中，我们一般需要数据的导入和导出，现在的产品都差不多，这些东西常见的。下面介绍用阿里巴巴的easyexcel实现excel数据导入 [阅读全文]
CAS与AQS

文章目录CASAQS（AbstractQueuedSynchronizer）CASCAS：Compare and... [阅读全文]
09.数据的条件查询操作

1. 条件查询WHERE筛选条件为true，则返回查询记录# 语法SELECT 查询列表 FROM 数据表名称 ... [阅读全文]
齐治堡垒机，功能诠释表！

堡垒机现如今走进很多企业或者是政府单位，在如今这个互联网的社会，也愈发让很多企业更加的重视安全，很多安全产品被广... [阅读全文]
SpringBoot引用阿里easyexcel，Excel导出返回浏览器下载

现在大的小的系统，各家的产品都差不多，一般运营或者产品规划的时候都会要求做一些导入导出数据的功能，他说供我统计或汇报用。好吧，我们苦逼的程序员开始干活了。 [阅读全文]
虚拟机下载apache2,解决虚拟机黑屏问题

这里写自定义目录标题虚拟机下载apache2虚拟机下载apache2更换代理在root下输入 wget... [阅读全文]
HashMap、Hashtable、ConcurrentHashMap三者间的异同

Hashtable 和 HashMap 的区别与联系1.两者都继承与map接口，所以两者的遍历方式大同小异2.H... [阅读全文]
等保测评--计算环境之终端设备安全

信息安全等级保护，是对信息和信息载体按照重要性等级分级别进行保护的一种工作，在中国、美国等很多国家都存在的一种信... [阅读全文]

网友评论


验证码：