当前位置:网站首页>Time complexity and space complexity
Time complexity and space complexity
2022-07-04 10:25:00 【sqjddb】
* The efficiency of the algorithm
After the algorithm is written into an executable program , Runtime needs Waste time, resources and space ( Memory ) resources . So measure the quality of an algorithm , Usually from Time and Space Measured in two dimensions , That is, time complexity and space complexity .
Time complexity mainly measures the performance of an algorithm Running fast or slow , The spatial complexity mainly measures the time required for the operation of an algorithm Extra space . In the early days of computer development , The storage capacity of the computer is very small . So I care about space complexity . But after the rapid development of the computer industry , The storage capacity of the computer has reached a high level . So now we don't need to pay special attention to the spatial complexity of an algorithm
* Time complexity
The time that an algorithm takes to execute , In theory , It can't be worked out , Only you put your program on the machine and run , To know . That's why we have the time complexity analysis . The time taken by an algorithm is proportional to the number of statements executed . In the algorithm Basic operation Number of executions , Time complexity of the algorithm , namely : Find a basic statement and the scale of the problem N Mathematical expressions between , Is to calculate the time complexity of the algorithm .
* Big O Asymptotic representation of
In practice, when we calculate the time complexity , We don't really have to calculate the exact number of execution , And it only takes about the number of times , Here we use Big O Asymptotic representation of .
Derivation is great O Order method :
1、 With constant 1 Replace all the addition constants in runtime .
2、 In the modified run times function , Only the highest order terms .
3、 If the highest order term exists and is not 1, The constant multiplied by this item is removed . The result is big O rank .
Big O The progressive representation of Remove those items that have little impact on the results , Simple and clear Indicates the number of executions
In addition, some algorithms have the best time complexity 、 Average and worst case :
The worst : Maximum number of runs of any input size ( upper bound )
On average : Expected number of runs of any input size
The best situation : Minimum number of runs of any input size ( Lower bound )
for example : At a length of N Search for a data in the array x
The best situation :1 Times found
The worst :N Times found
On average :N/2 Times found
In practice, the general concern is the worst-case operation of the algorithm , Therefore, the time complexity of searching data in the array is O(N)
* Time complexity of calculation
Here is a well written article that is very helpful to understand the calculation of complexity
example 1:
// Calculation BubbleSort Time complexity of ?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
example 5 Basic operations perform best N Time , At worst, it's executed (N*(N+1)/2 Time , By deducing the big O Order method + Time complexity is generally the worst , The time complexity is O(N^2)
example 2:
// Compute factorial recursion Fac Time complexity of ?
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}
Through calculation and analysis, it is found that the basic operation is recursive N Time , The time complexity is O(N)
example 3:
// Compute Fibonacci recursion Fib Time complexity of ?
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}
The time complexity can be approximated as 2^N
But strictly speaking In this way
* Spatial complexity
Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during operation . Space complexity is not how much the program takes up bytes Space , Because it doesn't make much sense either , So the space complexity is the number of open spaces .
The calculation rules of spatial complexity are basically similar to that of time complexity , Also use large O Asymptotic representation .
Be careful : Stack space required for function runtime ( Store parameters 、 local variable 、 Some register information, etc ) It has been determined during compilation , Therefore, the spatial complexity is mainly determined by the additional space explicitly requested by the function at run time .
* Computational space complexity
example 1:
// Calculation BubbleSort Spatial complexity of ?
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i-1] > a[i])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
We've used an extra space , So the space complexity is zero O(1)
example 2:
// Calculation Fibonacci Spatial complexity of ?
// Returns the first of the Fibonacci sequence n term
long long* Fibonacci(size_t n)
{
if(n==0)
return NULL;
long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; ++i)
{
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}
Dynamic opens up N Space , The space complexity is O(N)
example 3:
// Compute factorial recursion Fac Spatial complexity of ?
long long Fac(size_t N)
{
if(N == 0)
return 1;
return Fac(N-1)*N;
}
example 3 Recursively called N Time , Opens the N Stack frame , Each stack frame uses a constant space . The space complexity is O(N)
* Complexity comparison
边栏推荐
- Es advanced series - 1 JVM memory allocation
- Advanced technology management - how to design and follow up the performance of students at different levels
- 基于线性函数近似的安全强化学习 Safe RL with Linear Function Approximation 翻译 1
- Evolution from monomer architecture to microservice architecture
- 【Day2】 convolutional-neural-networks
- PHP代码审计3—系统重装漏洞
- Number of relationship models
- Devop basic command
- 使用 C# 提取 PDF 文件中的所有文字(支持 .NET Core)
- Qtreeview+ custom model implementation example
猜你喜欢
What are the advantages of automation?
Intelligent gateway helps improve industrial data acquisition and utilization
A little feeling
Devop basic command
leetcode1-3
Static comprehensive experiment ---hcip1
2. Data type
Some summaries of the third anniversary of joining Ping An in China
PHP code audit 3 - system reload vulnerability
Hands on deep learning (39) -- gating cycle unit Gru
随机推荐
Idea SSH channel configuration
BGP ---- border gateway routing protocol ----- basic experiment
Kotlin set operation summary
Dos:disk operating system, including core startup program and command program
Development guidance document of CMDB
System. Currenttimemillis() and system Nanotime (), which is faster? Don't use it wrong!
Realsense of d435i, d435, d415, t265_ Matching and installation of viewer environment
Service developers publish services based on EDAs
2. Data type
按键精灵打怪学习-识别所在地图、跑图、进入帮派识别NPC
Sword finger offer 31 Stack push in and pop-up sequence
leetcode1-3
Batch distribution of SSH keys and batch execution of ansible
Online troubleshooting
基于线性函数近似的安全强化学习 Safe RL with Linear Function Approximation 翻译 1
Pod management
【Day2】 convolutional-neural-networks
Work order management system OTRs
Press the button wizard to learn how to fight monsters - identify the map, run the map, enter the gang and identify NPC
uniapp---初步使用websocket(长链接实现)