1. 算法的复杂度:
算法的复杂度分为时间复杂度和空间复杂度,时间复杂度是指衡量算法执行时间的长短;空间复杂度是指衡量算法所需存储空间的大小。
2. 时间复杂度:
2.1 时间频度:一个算法中语句执行次数称为时间频度,计为T(n)。
2.2 时间复杂度:算法的时间复杂度描述的是T(n)的变化规律,计作:T(n)
= O(f(n))。
用大写O( )来体现算法复杂度的记法称为大O记法,一般情况下随着n的增大,T(n)增长最慢的算法为最优算法。
时间频度不同,但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。
2.3 推导大O阶:
(1)用常数1取代运行时间中的所有加法常数,如O(1)。
(2)在修改后的运行次数函数中,只保留最高阶数,如n²+n 为 O(n²)。
(3)如果最高阶数存在且不是1,则去除与这个项相乘的常数,如3n³ 为 O(n³)。
2.4 常见时间复杂度:
【1】常数阶:
/*
* 这个算法的运行次数是f(n)=3,与n的大小无关
* 根据推导大O阶的方法,常数项3改为1,即时间复杂度为O(1)
* 对于分支结构(不含循环结构),无论真或假,执行的次数都是恒定的
* 不会随着n的变大而发生变化,其时间复杂度也是O(1)
*/
int sum = 0, n = 100; // 执行一次
sum = (1 + n) * n / 2; // 执行一次
System.out.println(sum); // 执行一次
【2】
线性阶:
/* 时间复杂度为O(n),因为循环体中的代码要执行n次*/
for(int i = 0; i < n; i++){
;
}
【3】对数阶:
/*
* 每次count乘以2之后,就距离n更近了一分
* 有x个2相乘后大于n就会退出循环
* 由2的x次方等于n --> x = logn,时间复杂度为O(logn)
*/
int count = 1;
while(count < n){
count = count * 2;
}
【4】 平方阶:
/*
* 对应外层循环,不过是内部这个时间复杂度为O(n)的语句,在循环n次
* 所以这段代码的时间复杂度为O(n²)
*/
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
;
}
}
【5】对比图:
常用时间复杂度所耗费时间从小到大依次为:O(1)
< O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2n)
< O(n!) < O(nn)
2.5 最坏时间复杂度:
最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。
这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。
3. 空间复杂度:
算法的空间复杂度通过计算算法所需的存储空间实现,算法的空间复杂度的计算公式为: S(n) = O(f(n))。
通常没有特别指明时,复杂度指的是时间复杂度,我们写代码时,要学会以空间来换取时间。
分享到:
相关推荐
特别提醒:本文件为《大话数据分析:Tableau数据可视化实战》的数据集,并不是PDF书籍。
Android之大话设计模式——:抽象工厂模式借鉴.pdf
基于《大话数据结构》进行数据结构的学习
大话数据结构 .pptx
大话Oracle RAC:集群、高可用性、备份与恢复(带目录清晰中文完整版)
大话Oracle RAC:集群、高可用性、备份与恢复。 此书被认为不可多得的好资料之一:大话Oracle RAC(PDF经典),看完之后深有感触,发出来共享一下。
Android之大话设计模式——:抽象工厂模式参考.pdf
数据结构与算法问题 讲解生动 数据结构不在
《大话数据结构》——C语言简单实现单链表结构及相关一些操作
初中语文文摘历史“大话王”郭台铭:被夏普狠狠摔了个大跟
博主是第一次在CSDN上发动态的小白,由于大话数据结构这本书是用C实现的,对于Java才学到初级的我决定在后面学习的时候尽量用Java实现书中的例子,希望对这个事情感兴趣的同学一起加入,大家可以一起学习和探讨。...
查找算法,平衡二叉树,大话数据结构里面的。
《大话数据结构》———C语言简单实现KMP模式匹配算法
大话Oracle.RAC:集群、高可用性、备份与恢复(第2版)
大话存储2:存储系统架构与底层原理极限剖析》内容简介:网络存储是一个涉及计算机硬件以及网络协议/技术、操作系统以及专业软件等各方面综合知识的领域。目前国内阐述网络存储的书籍少之又少,大部分是国外作品,对...
大数据也可以定义为来自各种来源的大量非结构化或结构化数据。从学术角度而言,大数据的出现促成广泛主题的新颖研究。这也导致各种大数据统计方法的发展。大数据并没有统计学的抽样方法;它只是观察和追踪发生的事情...
数据结构
数据结构.mdaaa
《大话Oracle RAC:集群 高可用性 备份与恢复》以Oracle 10g为基础,对Oracle RAC进行了全面的介绍和分析。全书分为两个部分,共14章,第1部分是集群理论篇,这部分从集群基础知识入手,通过分析集群环境和单机环境...