当前位置:网站首页>Personal views on time complexity
Personal views on time complexity
2022-07-29 06:27:00 【C2024XSC249】
Concept
In computer science , time complexity , also called Time complexity , Algorithm Time complexity It's a function , It qualitatively describes the running time of the algorithm . This is a function of the length of the string representing the input value of the algorithm . Time complexity is often large O Symbolic representation , The lower order and first term coefficients of this function are not included . When using this method , Time complexity can be called asymptotic , That is, the size of the input value is approaching infinity .
Constant order
for example :
#include <cstdio>
using namespace std;
int main () {
int a, b;
scanf ("%d %d", &a, &b);
int c = a + b;
printf ("%d", c);
return 0;
}
This code , No matter what you enter a
and b
What is the value of , Will only run once , So write it down as Constant order : O ( 1 ) O (1) O(1)
Linear order
for example :
#include <cstdio>
using namespace std;
int main () {
int n, sum = 0;
scanf ("%d", &n);
for (int i = 1; i <= n; i ++) {
sum += n;
}
printf ("%d", sum);
return 0;
}
This code , The number of runs is determined by n
decision , So write it down as Linear order : O ( n ) O (n) O(n)
Square order
for example :
#include <cstdio>
using namespace std;
int main () {
int n, sum = 0;
scanf ("%d", &n);
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= n; j ++) {
sum += i * j;
}
}
printf ("%d", sum);
return 0;
}
This code , The number of runs is determined by n
decision , But there are two nested loops , So write it down as Square order : O ( n 2 ) O (n^{2}) O(n2)
Similarly , If nested k Secondary cycle , Write it down as k Order of second order : O ( n k ) O (n^{k}) O(nk)
Logarithmic order
for example :
#include <cstdio>
using namespace std;
int main () {
int n, sum = 0;
scanf ("%d", &n);
while (n != 0) {
n /= 2, sum ++;
}
printf ("%d", sum);
return 0;
}
This code , The number of runs is calculated n
How many of them 2
, So write it down as Logarithmic order : O ( log n ) O (\log n) O(logn)
Similarly , If we combine linear order and logarithmic order , Write it down as Linear logarithmic order : O ( n log n ) O (n \log n) O(nlogn)
Exponential order
for example :
#include <cstdio>
using namespace std;
long long digui (int n) {
if (n == 1 || n == 2) {
return 1;
}
return digui (n - 1) + digui (n - 2);
}
int main () {
int n, sum = 0;
scanf ("%d", &n);
for (int i = 1; i <= n; i ++) {
sum += n;
}
printf ("%d", sum);
return 0;
}
This code , Fibonacci series , Need to compute 2 n 2^{n} 2n Time ( No explanation here ), Write it down as Exponential order : O ( 2 n ) O (2^{n}) O(2n)
summary
About the analysis of time complexity, the author is here , If there are mistakes or omissions , Please bosses Don't hesitate to correct .
边栏推荐
- FTP的两种模式详解
- Mathematical modeling experience
- Leetcode 26. delete duplicates in the ordered array
- UE5 光影基础 阴影全解析 锯齿阴影解决方案 Lumen
- Unity-默认渲染管线-刻晴卡渲shader
- Leetcode 13. Roman numeral to integer
- Navicat for Oracle Cannot create oci environment
- Operating system interview questions
- 官方教程 Redshift 02 4中GI引擎概述及总结
- Eight sorts ----------- bubble sort
猜你喜欢
Leetcode 283. move zero
LeetCode #557.反转字符串中的单词 III
Leetcode 19. delete the penultimate node of the linked list
[beauty of software engineering - column notes] 19 | as a programmer, you should have product awareness
Joiner.on和stream().map联合使用技巧
Encapsulation - Super keyword
MySql-面试题
Leetcode - Tips
NoClassDefFoundError 处理
Computer network interview questions
随机推荐
Leetcode 189. rotation array
Learning notes of bit operation
Official tutorial redshift 04 rendering parameters
Operating system interview questions
动态规划总结
LeetCode #7.整数反转
Leetcode 977. Square of ordered array
虹科 | 使用JESD204串行接口高速桥接模拟和数字世界
官方教程 Redshift 02 4中GI引擎概述及总结
Eight sorts ----------- bubble sort
使用STP生成树协议解决网络中的二层环路问题
【Leetcode刷题】数组3——分治
Eight sorts --------- quick sort
2022暑初二信息竞赛学习成果分享2
Abstract classes and interfaces
Leetcode 14. longest public prefix
EtherCAT主站掉线后,如何保证目标系统免受故障影响?
文件系统一
[beauty of software engineering - column notes] 17 | what is the need analysis? How to analyze?
摊余成本最牛例子