您的当前位置:首 页 >> 信息中心

1������������������������,如何理解算法时间复杂度的表示法,例如 O(n²)、O(n)、O(1)、O(nlogn) 等?

发布日期:2021-09-28 19:38:06 作者: 点击:

一个程序在写出来之前是无法准确估计实际运行时间的。但是几乎所有算法竞赛的任务都会告知输入数据的规模和运行时间限制,这就允许选手通过分析算法的时间复杂度,从而事先估计能否在限定的时间内运行完程序。

下面一个例子也许可以让大家了解各种时间复杂度。为了使读者更加容易理解(初中水平的数学知识就能读懂,没有用到比较高级的数学工具),失去了部分严谨性,但足以运用到程序设计竞赛中。

例题:区间最大和

https://www.luogu.com.cn/problem/P5745

给定n个正整数组成的数列a_1,a_2,\cdots ,a_n和一个整数M 。要求从这个数列中找到一个子区间[i,j] ,也就是在这个数列中连续的数字a_i,a_{i+1},\cdots ,a_{j-1},a_j ,使得这个子区间的和在不超过M的情况下最大。输出ij和区间和。如果有多个区间符合要求,请输出i最小的那一个。对于所有测试数据, a_i\le 10^5,M\le10^9

例如,当输入是:

5 102 3 4 5 6

应当输出 1 3 9。

子任务 1(10分): n\le 200

子任务 2(20分): n\le 3000

子任务 3(30分): n\le 10^5

子任务 4(40分): n\le 4\times 10^6

请读者先尝试独立思考并完成这个题目,先不必考虑子任务是什么(实际上这很重要)。

什么是 O(n³) 算法?

思路 1:最直接的思路就是枚举所有子区间头尾 i 和 j,然后对 i 和 j 里面的所有数字累加起来求和,然后判断是否在不大于 M 的情况下最大。代码非常基础:

#includeusing namespace std;int a[10000150];int main() {int n, M;int ansmax = 0, ansi, ansj;cin >> n >> M;for (int i = 1; i > a[i];for (int i = 1; i