1. Time complexity
Definition: In computer science, the time of an algorithm Complexity is a function that quantitatively describes the running time of the algorithm. Theoretically speaking, the time it takes to execute an algorithm can only be known if you put your program on the machine and run it. However, we have a set of time complexity Analysis method of degree. The time spent by an algorithm is proportional to the number of executions of its statements. The number of executions of the basic operations in the algorithm is the time complexity of the algorithm.2. Time complexity Why not measure it in time instead of the number of times a basic statement is run?
The execution time of the algorithm depends on the specific software and hardware environment. Therefore, the time complexity of the algorithm cannot be measured by the length of execution time, but by the order of magnitude of the number of basic statement executions.3. The O asymptotic notation of time complexity (Big O notation)
is a mathematical symbol used to describe the asymptotic behavior of a function. Big O-order method derivation: Calculate the order of magnitude of the number of executions of a basic statement;
Only need to calculate the order of magnitude of the number of executions of a basic statement, which means that as long as the highest power in the function of the number of executions of a basic statement is guaranteed to be correct, that is Yes, all coefficients of lower powers and higher powers can be ignored. This simplifies algorithm analysis and focuses attention on the most important point: growth rate.
If the algorithm contains nested loops, the basic statement is usually the innermost loop body. If the algorithm contains parallel loops, the time complexity of the parallel loops is added. For example:
for (i=1; i The time complexity of the first for loop is Ο(n), the time complexity of the second for loop is Ο(n2), then the time complexity of the entire algorithm is Ο(n n2)=Ο(n2). <p></p><p> 4. Time complexity: optimal, average, worst case. Why does time complexity look at the worst case? <strong></strong></p> The worst-case complexity is the maximum resource consumed by all possible input data. If the worst-case complexity meets our requirements, we can guarantee that it will work in all cases. There will be no problem. <p></p> Some algorithms often encounter the worst case. For example, a search algorithm often needs to find a value that does not exist. <p> Maybe you think the complexity of the average case is more attractive to you, but there are several problems with the average case. First, it is difficult to calculate. The worst-case complexity of most algorithms is much easier to calculate than the average case. Second, the average-case and worst-case complexity of many algorithms are the same. Third, What is the true average? It is also unreasonable to assume that all possible input data have the same probability. In fact, most situations are different. And the distribution function of the input data is probably something you have no way of knowing. <br>It makes no sense to consider the complexity of the best case scenario. <br></p><p> 5. How to solve: the time complexity of binary search, recursive factorial, and recursive Fibonacci? <strong></strong></p> Binary search: The time complexity of searching through origami is O(logN);<p> Recursive factorial search: Recurse the basic operations N times to get the time complexity of O(N);<br> Recursive Fibonacci: Analysis shows that the basic operation is recursive 2<br>N times, and the time complexity is O(2<sup>N);</sup></p><p> 6. What is space complexity ? <strong></strong></p> Space complexity is a measure of the amount of storage space an algorithm temporarily occupies during operation. Space complexity is not how many bytes of space the program occupies, because this does not make much sense, so the space Complexity is calculated as the number of variables. The calculation rules of space complexity are basically similar to time complexity, and are also expressed using the big O asymptotic method.<p></p><p><strong> 7.如何求空间复杂度？ 普通函数&递归函数</strong></p><p style="line-height: 2em;"> 一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为 递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。</p><p style="line-height: 2em;"><strong> 8. 分析递归斐波那契数列的：时间、空间复杂度，并对其进行优化，伪递归优化—>循环优化</strong></p><pre class="brush:php;toolbar:false">long long Fib(int N) {
if (N <p> 普通递归实现的斐波那契数列:<br> 时间复杂度:O(2^n)<br><img src="https://img.php.cn/upload/article/000/000/051/79601e8681a1e563f3ddfcadebcb758c-0.png" alt="How to evaluate the quality of an algorithm"><br> 计算并根据<strong>O渐进表示法</strong>得出时间复杂度.</p><p> 空间复杂度:O(N);递归深度乘以(每一次递归的空间占用{有辅助空间或常量})</p><p> 伪递归优化:</p><pre class="brush:php;toolbar:false">long long fib (long long first, longlong second, int N) {
if(N <p> 时间复杂度:<br> O(N);<br> 递归深度乘以每次递归的循环次数<br> 空间复杂度:<br> O(1)或O(N)<br> 关键看编译器是否优化,优化则为O(1)否则O(N);</p><p> 循环优化:</p><pre class="brush:php;toolbar:false">long long Fib(int N) {
long long first = 1;
long long second = 1;
long long ret = 0;
for (int i = 3; i <p> 时间复杂度:O(N);</p><p> 空间复杂度:O(1);</p><p> <strong>9.常见时间复杂度</strong></p><p> 常见的算法时间复杂度由小到大依次为： Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!) Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。Ο(log2n)、Ο(n)、Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。</p><link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-60ecaf1f42.css" rel="stylesheet"><!-- flowchart 箭头图标 勿删 --><svg xmlns="http://www.w3.org/2000/svg" style="display: none;"><path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path></svg>The above is the detailed content of How to evaluate the quality of an algorithm. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
