文档章节

算法的时间复杂度

Cheuker
 Cheuker
发布于 2017/01/05 16:38
字数 1122
阅读 132
收藏 0

同一个问题有不同的解决方案,每一个方法解决一个问题的所花的时间的就是时间复杂度。当然执行次数越多,所花的时间就越多,所以我们可以通过执行次数来理解时间复杂度。

时间复杂度可以使用符号O(1),O(n),O(n²),O(n³),O(logn),O(nlogn),O(2^n)等等,特别说明一下,这只是符号而已,可以理解成一个变量就可以了。

接下来,我们来讲讲每一个时间复杂度到底是一个什么情况。

O(1)

假设我们现在有一个切片(goalng的叫法,php就叫索引数组)

array := [1]string{"a"}

那么问题来了,我从array中取出字符串a需要几次,不用计算就知道1次就够了,如下执行一次就输出了a:

fmt.Println(array[0]) //output a

这个array长度是1,现在我们array长度加长到3个,把a放到最后,现在这个数组是这样的:

array := [3]string{"c","b","a"}

当然,我们本知道a实际是就是array[2],还是一次就够了,这里假设a是第三个元素,我们不知道array[2]能够得出a,怎么办,循环:

for i := 0; i <= len(array); i++ {
		if array[i] == "a" {
			fmt.Println(array[i])
			break;
		}
}

找到a我们就退出,总共需要3次,就记作O(3),为了简单的好记就记作O(1)。到这里问题又来了,如果array长度是n呢,这里依然假设a是array的第三个元素,如果n不管有多长,我取到的a三次就够了!我们就把这种执行固定的次数的算法所花的时间叫做常数阶,实际就是时间复杂度O(1),还有一行代码可以通俗的表示:

sum := n+1 //这里不管n取什么值,这行求和计算,只需要计算一次,时间复杂度就是O(1)

使用数学的xy轴表示就是:

O(n)

继续讨论上面的问题,假设array中a不管n多大,也就是不管array数组有多长,a始终是在最后元素,那么

​
for i := 0; i <= n; i++ {
		if array[i] == "a" {
			fmt.Println(array[i])
			break;
		}
}

循环中,要想取到a,则需要循环n次,这种情况的时间复杂度就是记作O(n),也就是我要找到a,是随着n成线性增长的,叫做线性阶。如下

O(n²)

好了,现在我们有这样的一个循环累加r

package main

import "fmt"

func main() {
	n := 10
	r := 0
	for i := 1; i <= n; i++ {
		for j := 1; j <= n; j++ {
			r++
		}
	}
	fmt.Println(r)
}

很显然r累加的次数是n*n,就是n²次,这里的输出的结果就是100,作图

O(n³)

这个就不用解释了了吧,上面循环再套一层,来张图助助兴

O(logN)

先看下面的一段代码:

package main

import "fmt"

func main() {
	c := 1 //需要查找的数
	array := []int{1, 2, 3, 4, 5, 6, 7, 8} //有序的数组
	start := 0 //数组开始的索引起点
	end := 7 //数组结束的索引
	var mid int //中间的一个数组索引
	for start<= end {
		mid = (start + end + 1) / 2
		if c == array[mid] {
			fmt.Println("found!")
			break
		} else if (c > array[mid]) {
			start = mid + 1;
		} else if (c < array[mid]) {
			end = mid - 1;
		}
		fmt.Println("not found!")
	}
}

不难看出来,这块代码就是一个有序切片的二分查找,其时间复杂度就是O(logN),为什么是O(logN)怎么计算?

 假设该有序切片的长度是N那么二分后是N/2,再二分后是N/4,N/8……直到二分到1结束,设循环次数为x,假设我们现在最坏的情况下,一直循环到不能分割,即上面代码要查找c=1,就是最坏的情况,这里就有  则可以导出,要求得x,这就要引入对数了:

其他的就暂且不讨论

时间复杂度大小排序

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

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2^n)

列出一个图可以看的更清晰

© 著作权归作者所有

Cheuker
粉丝 0
博文 24
码字总数 5727
作品 0
厦门
高级程序员
私信 提问

暂无文章

golang-字符串-地址分析

demo package mainimport "fmt"func main() {str := "map.baidu.com"fmt.Println(&str, str)str = str[0:5]fmt.Println(&str, str)str = "abc"fmt.Println(&s......

李琼涛
40分钟前
3
0
Spring Boot WebFlux 增删改查完整实战 demo

03:WebFlux Web CRUD 实践 前言 上一篇基于功能性端点去创建一个简单服务,实现了 Hello 。这一篇用 Spring Boot WebFlux 的注解控制层技术创建一个 CRUD WebFlux 应用,让开发更方便。这里...

泥瓦匠BYSocket
今天
6
0
从0开始学FreeRTOS-(列表与列表项)-3

FreeRTOS列表&列表项的源码解读 第一次看列表与列表项的时候,感觉很像是链表,虽然我自己的链表也不太会,但是就是感觉很像。 在FreeRTOS中,列表与列表项使用得非常多,是FreeRTOS的一个数...

杰杰1号
今天
4
0
Java反射

Java 反射 反射是框架设计的灵魂(使用的前提条件:必须先得到代表的字节码的 Class,Class 类 用于表示.class 文件(字节码)) 一、反射的概述 定义:JAVA 反射机制是在运行状态中,对于任...

zzz1122334
今天
4
0
聊聊nacos的LocalConfigInfoProcessor

序 本文主要研究一下nacos的LocalConfigInfoProcessor LocalConfigInfoProcessor nacos-1.1.3/client/src/main/java/com/alibaba/nacos/client/config/impl/LocalConfigInfoProcessor.java p......

go4it
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部