Table of Contents
1. Time complexity
二、空间复杂度
Home Web Front-end JS Tutorial An article to talk about the time complexity and space complexity of the algorithm

An article to talk about the time complexity and space complexity of the algorithm

Mar 04, 2022 pm 03:45 PM
time complexity space complexity algorithm

This article will learn about the algorithm and introduce the time complexity and space complexity of the algorithm. I hope it will be helpful to everyone!

An article to talk about the time complexity and space complexity of the algorithm

Algorithm refers to a set of methods used to manipulate data and solve program problems. For the same problem, using different algorithms, the final result may be the same, but the resources and time consumed in the process will be very different.

So how should we measure the pros and cons of different algorithms?

Mainly consider it from the two dimensions of "time" and "space" occupied by the algorithm.

  • Time dimension: refers to the time consumed in executing the current algorithm. We usually use "time complexity" to describe it.

  • Space dimension: refers to how much memory space is required to execute the current algorithm. We usually use "space complexity" to describe it.

Therefore, evaluating the efficiency of an algorithm mainly depends on its time complexity and space complexity. However, sometimes time and space are "have your cake and eat it too" and you cannot have both, so we need to find a balance point.

Let me introduce the calculation methods of "time complexity" and "space complexity" respectively.

1. Time complexity

We want to know the "time complexity" of an algorithm. The first way many people think of is to run the algorithm program once. Then the time complexity it consumes Time will come naturally.

Is this method possible? Of course you can, but it also has many disadvantages.

This method is very susceptible to the influence of the operating environment. The results run on a high-performance machine will be very different from the results run on a low-performance machine. And it also has a lot to do with the scale of data used in testing. Furthermore, when we wrote the algorithm, we still had no way to run it completely.

Therefore, another more general method comes out: " Big O notation", that is, T(n) = O(f(n))

Let’s take a look at an example first:

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
Copy after login
Copy after login

Using "Big O notation", the time complexity of this code is: O(n), why?

In Big O notation, the formula for time complexity is: T(n) = O( f(n) ), where f(n) represents the sum of the number of executions of each line of code, and O represents Proportional relationship, the full name of this formula is: The asymptotic time complexity of the algorithm.

Let’s continue to look at the above example. Assume that the execution time of each line of code is the same. We use 1 particle time to express it. Then the first line of this example takes 1 particle time, and the third line of code takes 1 particle time. The execution time of the row is n granular time, and the execution time of the fourth row is also n granular time (the second and fifth rows are symbols, ignore them for now), then the total time is 1 granular time n granular time n granular time, that is (1 2n) particle time, that is: T(n) = (1 2n)*particle time. From this result, it can be seen that the time consumption of this algorithm changes with the change of n. Therefore, we can simplify Express the time complexity of this algorithm as: T(n) = O(n)

Why can it be simplified in this way? Because the big O notation is not used to truly represent the execution time of the algorithm. , which is used to represent the growth trend of code execution time.

So in the above example, if n is infinite, the constant 1 in T(n) = time(1 2n) is meaningless, and the multiple 2 is also meaningless. Therefore it can be simply simplified to T(n) = O(n).

Common time complexity metrics include:

  • Constant order O(1)

  • Logarithmic order O(logN )

  • Linear order O(n)

  • Linear logarithmic order O(nlogN)

  • square order O(n²)

  • cubic order O(n³)

  • ##Kth power order O(n^k)

  • Exponential order (2^n)

The time complexity from top to bottom is getting bigger and bigger, and the execution efficiency is getting lower and lower. .

Below we select some of the more commonly used ones to explain (not in strict order):

  • Constant order O(1)

No matter how many lines the code is executed, as long as there are no complex structures such as loops, the time complexity of this code will be O(1), such as:

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
Copy after login
Copy after login

When the above code is executed, its consumption does not increase with the growth of a certain variable, so no matter how long this type of code is, even if it has tens of thousands or hundreds of thousands of lines, it can use O(1) to express its time complexity.

  • Linear order O(n)

This is in the initial code example I have already explained it, such as:

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
Copy after login
Copy after login

In this code, the code in the for loop will be executed n times, so the time it consumes changes with the change of n, so this type of code can be used O(n) to represent its time complexity.

  • Logarithmic order O(logN)

Let’s look at the code first:

int i = 1;
while(i<n)
{
    i = i * 2;
}
Copy after login

从上面代码可以看到,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。我们试着求解一下,假设循环x次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n

也就是说当循环 log2^n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(logn)

  • 线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解,将时间复杂度为O(logn)的代码循环N遍的话,那么它的时间复杂度就是 n * O(logN),也就是了O(nlogN)。

就拿上面的代码加一点修改来举例:

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}
Copy after login
  • 平方阶O(n²)

平方阶O(n²) 就更容易理解了,如果把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。

举例:

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
Copy after login

这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O(n*n),即 O(n²)

如果将其中一层循环的n改成m,即:

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
Copy after login

那它的时间复杂度就变成了 O(m*n)

  • 立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环,其它的类似。

除此之外,其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法,有点复杂,这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的,那么我也应该明白,空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。

空间复杂度比较常用的有:O(1)、O(n)、O(n²),我们下面来看看:

  • 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

举例:

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
Copy after login
Copy after login

代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

  • 空间复杂度 O(n)

我们先看一个代码:

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
Copy after login

这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)

以上,就是对算法的时间复杂度与空间复杂度基础的分析,欢迎大家一起交流。

更多算法相关知识,请访问:编程入门!!

The above is the detailed content of An article to talk about the time complexity and space complexity of the algorithm. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance CLIP-BEVFormer: Explicitly supervise the BEVFormer structure to improve long-tail detection performance Mar 26, 2024 pm 12:41 PM

Written above &amp; the author’s personal understanding: At present, in the entire autonomous driving system, the perception module plays a vital role. The autonomous vehicle driving on the road can only obtain accurate perception results through the perception module. The downstream regulation and control module in the autonomous driving system makes timely and correct judgments and behavioral decisions. Currently, cars with autonomous driving functions are usually equipped with a variety of data information sensors including surround-view camera sensors, lidar sensors, and millimeter-wave radar sensors to collect information in different modalities to achieve accurate perception tasks. The BEV perception algorithm based on pure vision is favored by the industry because of its low hardware cost and easy deployment, and its output results can be easily applied to various downstream tasks.

Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Jun 03, 2024 pm 01:25 PM

Common challenges faced by machine learning algorithms in C++ include memory management, multi-threading, performance optimization, and maintainability. Solutions include using smart pointers, modern threading libraries, SIMD instructions and third-party libraries, as well as following coding style guidelines and using automation tools. Practical cases show how to use the Eigen library to implement linear regression algorithms, effectively manage memory and use high-performance matrix operations.

Explore the underlying principles and algorithm selection of the C++sort function Explore the underlying principles and algorithm selection of the C++sort function Apr 02, 2024 pm 05:36 PM

The bottom layer of the C++sort function uses merge sort, its complexity is O(nlogn), and provides different sorting algorithm choices, including quick sort, heap sort and stable sort.

Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Can artificial intelligence predict crime? Explore CrimeGPT's capabilities Mar 22, 2024 pm 10:10 PM

The convergence of artificial intelligence (AI) and law enforcement opens up new possibilities for crime prevention and detection. The predictive capabilities of artificial intelligence are widely used in systems such as CrimeGPT (Crime Prediction Technology) to predict criminal activities. This article explores the potential of artificial intelligence in crime prediction, its current applications, the challenges it faces, and the possible ethical implications of the technology. Artificial Intelligence and Crime Prediction: The Basics CrimeGPT uses machine learning algorithms to analyze large data sets, identifying patterns that can predict where and when crimes are likely to occur. These data sets include historical crime statistics, demographic information, economic indicators, weather patterns, and more. By identifying trends that human analysts might miss, artificial intelligence can empower law enforcement agencies

Improved detection algorithm: for target detection in high-resolution optical remote sensing images Improved detection algorithm: for target detection in high-resolution optical remote sensing images Jun 06, 2024 pm 12:33 PM

01 Outlook Summary Currently, it is difficult to achieve an appropriate balance between detection efficiency and detection results. We have developed an enhanced YOLOv5 algorithm for target detection in high-resolution optical remote sensing images, using multi-layer feature pyramids, multi-detection head strategies and hybrid attention modules to improve the effect of the target detection network in optical remote sensing images. According to the SIMD data set, the mAP of the new algorithm is 2.2% better than YOLOv5 and 8.48% better than YOLOX, achieving a better balance between detection results and speed. 02 Background & Motivation With the rapid development of remote sensing technology, high-resolution optical remote sensing images have been used to describe many objects on the earth’s surface, including aircraft, cars, buildings, etc. Object detection in the interpretation of remote sensing images

How to analyze the time complexity of C++ recursive functions? How to analyze the time complexity of C++ recursive functions? Apr 17, 2024 pm 03:09 PM

Time complexity analysis of recursive functions involves: identifying base cases and recursive calls. Calculate the time complexity of the base case and each recursive call. Sum the time complexity of all recursive calls. Consider the relationship between the number of function calls and the size of the problem. For example, the time complexity of the factorial function is O(n) because each recursive call increases the recursion depth by 1, giving a total depth of O(n).

Application of algorithms in the construction of 58 portrait platform Application of algorithms in the construction of 58 portrait platform May 09, 2024 am 09:01 AM

1. Background of the Construction of 58 Portraits Platform First of all, I would like to share with you the background of the construction of the 58 Portrait Platform. 1. The traditional thinking of the traditional profiling platform is no longer enough. Building a user profiling platform relies on data warehouse modeling capabilities to integrate data from multiple business lines to build accurate user portraits; it also requires data mining to understand user behavior, interests and needs, and provide algorithms. side capabilities; finally, it also needs to have data platform capabilities to efficiently store, query and share user profile data and provide profile services. The main difference between a self-built business profiling platform and a middle-office profiling platform is that the self-built profiling platform serves a single business line and can be customized on demand; the mid-office platform serves multiple business lines, has complex modeling, and provides more general capabilities. 2.58 User portraits of the background of Zhongtai portrait construction

How to deal with time complexity issues in PHP functions? How to deal with time complexity issues in PHP functions? Apr 26, 2024 pm 02:12 PM

Time complexity is a measure of how long a function takes to execute. Common PHP function time complexity problems include nested loops, large array traversals, and recursive calls. Techniques for optimizing time complexity include: using caching to reduce the number of loops simplifying algorithms using parallel processing

See all articles