算法分析——时间复杂度
时间复杂度
定义&意义
- 一行代码运行的时间*该行运行次数（对所有行执行次运算）
- 描述一个算法的快慢性能（假设在同样算力的计算机上，且没有其他任务消耗计算机任务的理想情况下）
- 约定用T(N) 表示所有主要语句的运行时间 ，单位时间为单位
- 将T(N)近似后用O(f(N)) 表示，其中，f(N) ~ F(N)
用一个例子简单说明
点击查看代码
int a= 10 ;
for(i =0 ;
i < a ;
i++){
System.out.println(i);
}- 第一行执行一次 ；记n
- 第二行中 ，i = 0 执行一次, i < a 执行11次，10次符合条件，1次判断越界，i++ 执行10次；分别记作 n、11n、10n
- 第三行中，执行10次 ，记10n
- 由此T(N) = 1n+1n+11n+10n+10n
显眼从数学上说是个一次函数，也就是说改程序段的时间复杂度是线性的，由此推知，当时嵌套的二重、三重ffor循环时，其复杂度应为平方级别，立方级别
- 当遇到较复杂的程序时，其运行时间取决于执行最频繁的语句（e.g.：三重for循环时间主要取决于最内层的语句）
相当于说办事情要抓主要矛盾了哈哈
【算法分析——时间复杂度】推算和证明用到一点求极限和基础数学知识，不是本文讨论的重点，故只列出结果
- 常数级别
- 对数 ：典型的二分查找
- 线性对数 典型并归排序
- 指数级别（只在某些特殊问题上有讨论价值，不能用于解决大问题，太慢）
推荐阅读
- C语言全排列回溯算法介绍
- 笔记|工业缺陷检测项目实战(一)——基于opencv的工件缺陷检测C++实现
- 图像处理|opencv使用相机标定——实战篇（附代码与可执行程序并解决程序崩溃问题）
- 边缘检测robert原理_基于OpenCV的车道线检测算法(Traditional Method)
- OpenCV|OpenCV项目实战——虚拟画笔
- 『现学现忘』Docker基础|『现学现忘』Docker基础 — 29、Docker容器数据卷的应用
- 每日算法之数组（一）
- 剑指Offer之Java算法习题精讲链表与数组专项训练
- 算法|有关for(auto x: vector＜int＞v)的问题
- 算法|746. 使用最小花费爬楼梯