同步操作将从 turnon/blog 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
title: 复杂度分析
date: 2022-03-20 23:25:17
categories:
- 数据结构和算法
- 综合
tags:
- 数据结构
- 算法
permalink: /pages/cba821/
衡量算法的优劣,有两种评估方式:事前估计和后期测试。
后期测试有性能测试、基准测试(Benchmark)等手段。
但是,后期测试有以下限制:
所以,需要一种方法,可以不受环境或数据规模的影响,粗略地估计算法的执行效率。这种方法就是复杂度分析。
假设问题的规模为 n,则程序的时间复杂度表示为 T(n)
。代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
当 n 增大时,T(n) 也随之增大,想要准确估计其变化比较困难。所以,可以采用大 O 时间复杂度来粗略估计其复杂度,其表达式为:T(n) = O(f(n))
。
大 O 表示法实际上并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势,所以,也叫作渐进时间复杂度(asymptotic time complexity),简称时间复杂度。
【示例】从 1 累加到 100 的时间复杂度是多少?
int sum = 0;
int N = 100;
for (int i = 1; i <= N; i++) {
sum = sum + i;
}
时间复杂度计算:显然,这段代码执行了 100 次加法,其时间复杂度和 N 的大小完全一致
T(n) = O(n)
【示例】嵌套循环的时间复杂度是多少?
int M = 10;
int N = 20;
for (int i = 1; i < M; i++) {
for (int j = 1; j < N; j++) {
System.out.println("i = " + i + ", j = " + j);
}
}
时间复杂度计算:
T(n) = (M-1)(N-1) = O(M*N) ≈ O(N^2)
【示例】递归函数的时间复杂度是多少?思考一下斐波那契数列 f(n) = f(n-1) + f(n-2)
的时间复杂度是多少?
T(n) = O(2^N)
时间复杂度的全称是渐进时间复杂度,表示算法的执行时间与数据规模之间的增长关系。
类比一下,空间复杂度全称就是渐进空间复杂度(asymptotic space complexity),表示算法的存储空间与数据规模之间的增长关系。
复杂度有以下量级:
O(1)
:常数复杂度O(log n)
:对数复杂度O(n)
:线性复杂度O(nlog n)
:线性对数阶复杂度O(n^2)
:平方复杂度O(n^3)
:立方复杂度O(n^k)
:K 次方复杂度O(2^n)
:指数复杂度O(n!)
:阶乘复杂度在数据量比较小的时候,复杂度量级差异并不明显;但是,随着数据规模大小的变化,差异会逐渐突出。
O(1)
复杂度示例:
int num = 100;
System.out.println("num = " + num);
O(log n)
对数复杂度示例:
int max = 100;
for (int i = 1; i < max; i = i * 2) {
System.out.println("i = " + i);
}
O(n)
复杂度示例:
int max = 100;
for (int i = 1; i < max; i++) {
System.out.println("i = " + i);
}
O(n^2)
复杂度示例:
int M = 10;
int N = 20;
for (int i = 1; i < M; i++) {
for (int j = 1; j < N; j++) {
System.out.println("i = " + i + ", j = " + j);
}
}
O(k^n)
复杂度示例:
int max = 10;
for (int i = 1; i <= Math.pow(2, max); i++) {
System.out.println("i = " + i);
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。