如何評價一個演算法的好壞

#    首先，這個演算法必須是正確的

#其次，好的演算法應該是友善的，便於人們理解和交流，並且是機器可執行的。

    這個演算法還需要足夠健壯，即當輸入的資料非法或不合理時，也能適當的做出正確的反應或進行相應的處理

    最後它也必須擁有高效率和低存儲量要求。

    也就是所謂的時間複雜度與空間複雜度

    1.時間複雜度

##    定義:在電腦科學,演算法的時間複雜度是一個函數,他定量描述了該演算法的運行時間.一個演算法執行所耗費的時間,從理論上講,只有你把你的程式放機器上跑起來,才能知道.然而我們有一套時間複雜度的分析方式.一個演算法所花費的時間與其中語句的執行次數成正比例.演算法中的基本運算的執行次數,為演算法的時間複雜度.

    2.時間複雜度為什麼不使用時間來衡量而使用基本語句的運行次數來衡量？

    演算法的執行時間取決於特定的軟硬體環境，所以，不能用執行時間的長短來衡量演算法的時間複雜度，而要透過基本語句執行次數的數量級來衡量。

    3.時間複雜度的O漸進表示法(Big O notation)

    是用來描述函數漸進為的數學符號.

#大O階方法推導:

    計算基本語句的執行次數的數量級；　
    只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次方正確即可，可以忽略所有低次方和最高次方的係數。這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：成長率。
　如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間複雜度相加。例如：

　for (i=1; i    第一個for迴圈的時間複雜度為Ο(n)，第二個for迴圈的時間複雜度為Ο(n2)，則整個演算法的時間複雜度為Ο(n n2)=Ο(n2)。 <p></p><p>    4.時間複雜度的:最適、平均、最差狀況，為什麼時間複雜度看的是最差狀況？ <strong></strong></p>    最差情況下的複雜度是所有可能的輸入資料所消耗的最大資源，如果最差情況下的複雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。 <p></p>    某些演算法常常會遇到最差情況。例如一個查找演算法，經常需要找一個不存在的值。 <p>    也許你覺得平均情況下的複雜度更吸引你，可是平均情況也有幾點問題。第一，難計算，多數演算法的最差情況下的複雜度要比平均情況下的容易計算的多，第二，有很多演算法的平均情況和最差情況的複雜度是一樣的. 第三，什麼才是真正的平均狀況？如果你假設所有可能的輸入資料出現的機率是一樣的話，也是不合理的。其實多數情況是不一樣的。而且輸入資料的分佈函數很可能是你沒辦法知道。 <br>考慮最好情況的複雜度更是沒有意義。 <br></p><p>    5.如何求解：二分查找、遞歸求階乘、遞歸斐波那契的時間複雜度？ <strong></strong></p>    二分查找:透過摺紙找出解時間複雜度為O(logN);<p>    遞歸階乘:數基本運算遞迴N次得到時間複雜度為O(N);<br>    遞歸斐波那契:分析得出基本運算遞歸了2<br>N次,時間複雜度為O(2<sup>N);</sup></p><p>    6.什麼是空間複雜度？ <strong></strong></p>    空間複雜度是對一個演算法在運作過程中暫時佔用儲存空間大小的量測.空間複雜度不是程式佔用了多少bytes的空間,因為這個也沒太大意義,所以空間複雜度算的是變數的個數.空間複雜度計算規則基本跟時間複雜度類似,也使用大O漸進法表示.<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="如何評價一個演算法的好壞"><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>

以上是如何評價一個演算法的好壞的詳細內容。更多資訊請關注PHP中文網其他相關文章！