Shulou(Shulou.com)05/31 Report--

This article mainly explains "C language data structure algorithm time complexity example analysis", the explanation content in the article is simple and clear, easy to learn and understand, please follow the small series of ideas slowly in-depth, together to study and learn "C language data structure algorithm time complexity example analysis" bar!

1. Complexity of the algorithm

After the algorithm is written into an executable program, it needs to consume time resources and space (memory) resources when running. Therefore, to measure the quality of an algorithm, it is generally measured from two dimensions of time and space, namely time complexity and space complexity.

Time complexity measures how fast an algorithm runs, while space complexity measures how much extra space an algorithm needs to run. In the early days of computer development, the storage capacity of computers was small. So I'm very concerned about spatial complexity. However, with the rapid development of computer industry, the storage capacity of computer has reached a very high level. So we no longer need to pay special attention to the spatial complexity of an algorithm. (This article focuses on time complexity.)

Time complexity 2.1 Definition of time complexity

Definition of time complexity: In computer science, the time complexity of an algorithm is a function that quantitatively describes the running time of the algorithm. The time it takes for an algorithm to execute is theoretically impossible to calculate, only if you run your program on a machine. But do we need to test every algorithm? It can be tested on the computer, but this is very troublesome, so there is a time complexity analysis method. The time taken by an algorithm is directly proportional to the number of executions of the statements in it, and the number of executions of the basic operations in the algorithm is the time complexity of the algorithm.

Examples:

How many times has the ++count statement in Func1 been executed?

void Func1(int N){int count = 0;for (int i = 0; i

< N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}printf("%d\n", count);} 时间复杂度函数：F(N)=N*N+2*N+10 实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。 2.2 大O的渐进表示法 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号 1、用1来代替常数,F(N)函数只有常数 O(1) 2、在运行次数中，只保留最高阶。 F(N)=N^3+N^2 -->

O(N^3)

3. The highest coefficient is reduced to 1. F(N) = 2*N --> O(N)

Note: When complexity is not fixed, time complexity looks at the worst case (pessimistic estimate).

For example: Search for a data x in an array of length N

Best case scenario: 1 find

Worst case: N times found

Average: N/2 finds

In practice, we usually focus on the worst-case operation of the algorithm, so the time complexity of searching the data in the array is O(N).

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;}}

F(N)= O(N^2)

3.2 int binarySearch(int* a, int n, int x){assert(a);int begin = 0;int end = n ;while (begin

< end){int mid = begin + ((end - begin) >

> 1);if (a[mid]

< x)begin = mid + 1;else if (a[mid] >

x)end = mid; elseturn mid;}return -1;}//left closed right closed int BinarySearch(int* a, int n, int x){assert(a);int begin = 0;int end = n-1;while (begin > 1);if (a[mid]

< x)begin = mid + 1;else if (a[mid] >

x)end = mid-1;elsereturn mid;}return -1;}

Suppose you find x times:

1*2*2*2*2......* 2 = N

2^x = N

x = log2 N

Worst case: O(log2 N) abbreviated to log(N)

3.3 Time Complexity of Factorial (Recursive)

O(1) is the number of times a function is called.

O(n) is the number of times a function is called, and O(n) is the number of times it is called.

long long Fac(size_t N){if (0 == N)return 1;return Fac(N - 1) * N;}

F(N) = O(N)

3.4 The time complexity of Fibonacci sequence long long Fib(size_t N){if (N

< 3)return 1;return Fib(N - 1) + Fib(N - 2);}

By calculation and analysis, it is found that the basic operation recurses 2^N times, and the time complexity is O(2^N).

Thank you for reading, the above is the "C language data structure algorithm time complexity example analysis" content, after learning this article, I believe we have a deeper understanding of the C language data structure algorithm time complexity example analysis this problem, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.