五分钟理解算法的时间复杂度

Dear 丶 2022-01-20 12:51 228阅读 0赞

#     #

## 前言 ##

时间复杂度主要是为了反映函数的执行时间随着输入规模增长而变化的规律，在一定程度上可以体现程序的执行效率和算法的优劣。作为程序员，掌握基本的算法时间复杂度的计算是很有必要的。

## 时间复杂度介绍 ##

理论上，执行一个算法消耗的时间，是无法精确计算的，即使上机测试，收到各种因素影响，得到的时间也可能有较大差别。对于程序员，我们只需关注哪个算法花费的时间多，哪个算法花费的时间少就可以了。

针对执行时间，我们可以根据算法执行的语句的次数，进行一个简单的衡量。理论上，一个算法中语句执行次数多，它花费时间相对也多，因此，算法运行的时间与算法中语句的执行次数成正比。我们将算法中的语句的执行次数称为时间频度，表示为T(n)，其中，n表示算法的输入规模，n的变化会引起T(n)的改变。

为了得到T(n)变化时表现的规律，我们引入时间复杂度的概念。若有某个函数f(n),当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，表示为T(n)=Ｏ(f(n))，Ｏ(f(n))称为算法的渐进时间复杂度，简称时间复杂度。

## 举例说明如何得到时间复杂度 ##

场景1：

1. **public** **int** func() \{

2. **int** a = 10 + 20; // 执行 1 次

3. **return** a; // 执行 1 次

4. \}

T(n) = 1 + 1 = 2

由于是常数，时间复杂度为O(1)

场景2：

1. **public** **void** func() \{

2. **int** n = 10; // 执行1次

3. **for**(**int** i = 0; i < n; i++) \{ // 执行 n 次

4. System.out.printf(i); // 执行 n 次

5. \}

6. \}

T(n) = n + n + 1 = 2n + 1

忽略常数项1，忽略和最高阶相乘的常数2，得到时间复杂度O(n)

其实，还可以先计算每个语句的时间复杂度，然后汇总：

1. **public** **void** func() \{

2. **int** n = 10; // 时间复杂度O(1)

3. **for**(**int** i = 0; i < n; i++) \{ // 时间复杂度O(n)

4. System.out.printf(i); // 时间复杂度O(1)

5. \}

6. \}

O(1 \* n \* 1) = O(n)

场景3：

1. **public** **int** func(**int** n) \{

2. **for**(**int** i = 0; i < n; i++) \{ // 执行n次

3. **for**(**int** j = 0; j < n; j++) \{ //由于外层循环，该语句执行 n \* n 次

4. System.out.printf("Hello"); // 同理，执行n\*n次

5. \}

6. \}

7. \}

T(n) = n + n^2 + n^2 = 2n^2 + n

忽略低阶项，和高阶项的常数部分，得到时间复杂度O(n^2)

场景4：

1. **public** **int** func(**int** n) \{

2. **for**(**int** i = 0; i < n; i = i\* 2) \{ // i=2,4,8,16...时执行，可通过对数近似计算次数，执行log2(n)次

3. System.out.printf("Hello");

4. \}

5. \}

T(n) = 2log2(n)

忽略常数部分，得到时间复杂度O(log2(n))

## 总结 ##

计算时间复杂度时，可以先先计算 T(n)，然后忽略常数项，只保留最高次项，同时忽略最高项的系数，得到函数 f(n)，则算法的时间复杂度就是 O(f(n))。

发表评论取消回复

表情：

评论列表（有 0 条评论，228人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】时间复杂度，空间复杂度

文章目录一：时间频度 1.1 度量一个程序(算法)执行时间的两种方法 1.2 基本介绍 1.3 举例说明

骑猪看日落/ 2024年03月02日 10:11/ 0 赞/ 62 阅读

相关十分钟搞定时间复杂度（算法的时间复杂度）

十分钟搞定时间复杂度（算法的时间复杂度）我们假设计算机运行一行基础代码需要执行一次运算。 int aFunc(void) {

我就是我/ 2023年10月02日 10:40/ 0 赞/ 12 阅读

相关 [时间复杂度]-排序算法的时间复杂度

我们经常可以看到这样的描述：软件=数据结构+算法，可见算法基础对于一个程序员的重要性。算法中，有两个基本概念：时间复杂度和空间复杂度。时间复杂度：描述算法执行消耗的时

今天药忘吃喽~/ 2023年09月24日 14:38/ 0 赞/ 84 阅读

相关算法的时间复杂度&空间复杂度

算法的衡量指标：在正确性的前提下，重点关注以下指标: （1）时间性能——运行算法所需的时间开销。（2）空间性能——运行算法所需的辅助空间的规模。

你的名字/ 2023年02月26日 07:24/ 0 赞/ 212 阅读

相关 1分钟学会计算算法的时间复杂度

数据结构中算法的时间复杂度，个人认为十分体系化，理解需要一点时间，下面让你1分钟学会计算算法的时间复杂度 1. 找出该算法运行次数最多的语句 2. 如果运行次数是常量，得

水深无声/ 2022年05月30日 11:35/ 0 赞/ 167 阅读

相关转：（数据结构）十分钟搞定时间复杂度（算法的时间复杂度）

我们假设计算机运行一行基础代码需要执行一次运算。 int aFunc(void) { printf("Hello, World!\n");

电玩女神/ 2022年05月24日 13:28/ 0 赞/ 185 阅读

相关（数据结构）十分钟搞定时间复杂度（算法的时间复杂度）

[https://www.jianshu.com/p/f4cca5ce055a][https_www.jianshu.com_p_f4cca5ce055a] [https_

àì夳堔傛蜴生んèń/ 2022年05月09日 13:50/ 0 赞/ 219 阅读

相关算法 - 空间复杂度时间复杂度

[关于算法空间复杂度的问题][Link 1] ‘算法空间复杂度’，别以为这个东西多么高大上，我保证你看完这篇文章就能明白。最近在啃算法，发现非常有趣。在我学习的

Bertha 。/ 2022年04月08日 08:29/ 0 赞/ 374 阅读

相关五分钟理解算法的时间复杂度

前言时间复杂度主要是为了反映函数的执行时间随着输入规模增长而变化的规律，在一定程度上可以体现程序的执行效率和算法的优劣。作为程序员，掌握基本的算法时间复杂

Dear 丶/ 2022年01月20日 12:51/ 0 赞/ 229 阅读

相关（数据结构）十分钟搞定时间复杂度（算法的时间复杂度）

[https://www.jianshu.com/p/f4cca5ce055a][https_www.jianshu.com_p_f4cca5ce055a] [https_

刺骨的言语ヽ痛彻心扉/ 2021年11月02日 05:38/ 0 赞/ 453 阅读