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

This article mainly introduces "case analysis of time complexity and space complexity of C language". In daily operation, I believe that many people have doubts about the case analysis of time complexity and space complexity of C language. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts of "case analysis of time complexity and space complexity of C language". Next, please follow the editor to study!

Concept 1.1, algorithm efficiency

How to measure the quality of an algorithm? For example, for the following Fibonacci series:

Long long Fib (int N) {if (N)

< 3) return 1; return Fib(N - 1) + Fib(N - 2);} 斐波那契数列用递归实现方式非常简洁，但简洁一定好吗？那该如何衡量其好与坏呢？在学完时间复杂度会为您揭晓。 算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度 1.2、时间复杂度 一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。 1.3、空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 二、计算2.1、大O的渐进表示法 先看一串代码： // 请计算一下Func1基本操作执行了多少次？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);} 算法中的基本操作的执行次数，为算法的时间复杂度。显而易见，这里Func1 执行的最准确操作次数 ：F(N)=N*N+2*N+10 例如F(10)=130、F(100)=10210、F(1000)=1002010 按理来说此题的时间复杂度就是上述的公式，其实不然。时间复杂度是一个估算，是去看表达式中影响最大的那一项。此题随着N的增大，这个表达式中N^2对结果的影响是最大的 实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次 数，那么这里我们使用大O的渐进表示法。，因而上题的时间复杂度为O(N^2) 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。 推导大O阶方法： 用常数1取代运行时间中的所有加法常数。 在修改后的运行次数函数中，只保留最高阶项。 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况： 最坏情况：任意输入规模的最大运行次数(上界) 平均情况：任意输入规模的期望运行次数 最好情况：任意输入规模的最小运行次数(下界) 例如：在一个长度为N数组中搜索一个数据x 最好情况：1次找到 最坏情况：N次找到 平均情况：N/2次找到 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N) 注意：递归算法时间复杂度计算 每次函数调用是O(1)，那么就看他的递归次数 每次函数调用不是O(1)，那么就看他的递归调用中次数的累加 2.2、时间复杂度计算 例题： 例一： // 计算Func2的时间复杂度？void Func2(int N){ int count = 0; for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count);} 答案：O(N) 解析：此题中最准确的次数为2*N+10，而其中影响最大的是N，可能有人觉着是2*N，但随着N的不断增大，2对结果的影响不是很大，况且要符合上述第三条规则：如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。所以把2去除掉，因而时间复杂度为O(N) 例二： // 计算Func3的时间复杂度？void Func3(int N, int M){ int count = 0; for (int k = 0; k < M; ++k) { ++count; } for (int k = 0; k < N; ++k) { ++count; } printf("%d\n", count);} 答案：O(M+N) 解析：因为M和N都是未知数，所以N和M都要带着，但是如果题目明确M远大于N，那么时间复杂度就是O(M)，如果M和N差不多大，那么时间复杂度就是O(M)或O(N) 例三： // 计算Func4的时间复杂度？void Func4(int N){ int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count);} 答案：O(1) 解析：这里最准确的次数是100，但是要符合大O的渐进表示法的规则，用常数1取代运行时间中的所有加法常数。所以时间复杂度就是O(1) 例四： // 计算strchr的时间复杂度？const char* strchr(const char* str, char character){ while (*str != '\0') { if (*str == character) return str; ++str; } return NULL;} 答案：O(N) 解析：此题就要分情况了，这里假设字符串为abcdefghijklmn，如果目标字符找的是g，则需要执行N/2次，如果找到是a，则需要执行1次，如果找n，则N次，所以要分情况，这里就出现了有些算法的时间复杂度存在最好O(1)、平均O(N/2)和最坏O(N)情况，但是在实际中一般情况关注的是算法的最坏运行情况，所以此题时间复杂度为O(N) 例五： // 计算BubbleSort的时间复杂度？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;}}

Answer: O (N ^ 2)

Parsing: this code deals with bubble sorting. The first trip has gone N times in bubble order, the second has gone to Nmuri once, and the third has gone to Nmuri 2,. Finally, there is 1, the secondary law is exactly the equidifference sequence, and the sum is (Number1) * Nmax 2. Of course, this is the most accurate, and here we have to find the term that has the greatest impact on the result, that is, N ^ 2, so the time complexity is O (N ^ 2).

Example 6:

/ / calculate the time complexity of BinarySearch? 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; else return mid;} return-1;}

Answer: O (logN)

Analysis: it is obvious that this question is a binary search. Suppose the length of the array is N, and you find it X times, then 1 / 2 / 2 / 2 / 2 *. * 2 ^ N, that is, 2 ^ X = N, then X is equal to the logarithm of log with 2 as base N, and the complexity of the algorithm likes to be omitted as logN, because it is difficult to write base numbers in many places, so the time complexity of this problem is O (logN).

Example 7:

/ / calculate the time complexity of factorial recursive Factorial? Long long Factorial (size_t N) {return N

< 2 ? N : Factorial(N-1)*N;} 答案：O(N) 解析：如果N为10 例八： long long Fib(int N){ if (N < 3) return 1; return Fib(N - 1) + Fib(N - 2);} 这串代码是上文最开始呈现的代码，代码风格十分简单，短短几行便可完成斐波那契数列的计算，可看似这么简洁的代码真的"好"吗？先来计算一下时间复杂度： 答案：O(2^N) 解析： 有上图可以得知，第一行执行1次，第二行执行2^1次，第三行执行2^2次，以此类推，是个等比数列，累计算下来再根据大O阶表示法的规则得知，此斐波那契数列的时间复杂度为O(2^N)。 但是，根据2^N这个时间复杂度是个非常大的数字，当n=10时，在VS环境下很快容易得到答案，但是当n稍微再大一点比如说是50，就要等上很长一段时间才能将结果算出来，由此可见，简洁的代码不一定是最优的代码。 常见时间复杂度：O(N^2)、O(N)、O(logN)、O(1) 复杂度对比： 2.3、空间复杂度计算 空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。 注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 例题 例一： // 计算BubbleSort的空间复杂度？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;}}

Answer: O (1)

Analysis: in fact, a total of three spaces have been opened up here, namely end, exchange, and I. since it is a constant variable, the space complexity is O (1). The space complexity calculates the extra space applied for, so it has nothing to do with int*an and int n above. Some people may think that this is a for cycle, exchange should be opened n times, in fact, each time the loop comes in, exchange will re-open, ending a cycle exchange destruction, and so on, exchange is always the same space.

And when will O (n) appear?

1. Malloc an array

Int* a = (int*) malloc (sizeof (int) * numsSize); / / O (N)

The premise of this situation is that numsSize must be an unknown number. If it is a specific number, then the space complexity is still O (1).

2. Variable length array

Int a [numsSize]; / / numsSize unknown, O (N)

Example 2:

/ / calculate the space complexity of Fibonacci? / returns the first n terms of the Fibonacci series 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

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.