2.3兩種算法的比較

?

#include <iostream> #if 0 //需要運(yùn)行 100次 int main() {int i,sum=0,n=100;for(i=1;i<=n;i++){sum=sum+i;} std::cout << sum;return 0; } #endif #if 1 int main() {//運(yùn)行一次 int sum=0,n=100;sum=(1+n)*n/2;std::cout << sum; } #endif //顯然 第二個(gè)算法更優(yōu)秀 //算法：解決特定問題求解的描述， 在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作2.4算法定義

? 算法是解決特定問題求解步驟的描述，在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。

2.5算法的特性

? 輸入輸出：零個(gè)或多個(gè)輸入，至少一個(gè)或多個(gè)輸出。

?有窮性：有限的步驟，每個(gè)步驟在可接受的時(shí)間內(nèi)完成

確定性：每一步都有確定的含義，沒有二義性

可行性：每一步都必須可行，執(zhí)行有限次數(shù)完成

2.6算法的設(shè)計(jì)

?正確性

?可讀性

?健壯性

時(shí)間效率高和存儲(chǔ)量低

2.7算法效率的度量方法

?2.7.1事后統(tǒng)計(jì)方法：通過寫好的測試程序和數(shù)據(jù)，利用計(jì)算機(jī)對(duì)不同算法比較，然后確定效率

???? 缺點(diǎn)：必須事先把程序?qū)懞?#xff0c;時(shí)間的快慢依賴計(jì)算機(jī)，算法測試數(shù)據(jù)設(shè)計(jì)困難

2.7.2事前分析估計(jì)方法 ：編程前對(duì)程序進(jìn)行估計(jì)

??? 缺點(diǎn)：依賴算法的好壞

2.10常見的時(shí)間復(fù)雜度

?? ? O(1): 表示算法的運(yùn)行時(shí)間為常量
? ? O(n): 表示該算法是線性算法
?? O(㏒₂n): 二分查找算法
?? O(n²): 對(duì)數(shù)組進(jìn)行排序的各種簡單算法，例如直接插入排序的算法。
?? O(n³): 做兩個(gè)n階矩陣的乘法運(yùn)算
?? O(2ⁿ): 求具有n個(gè)元素集合的所有子集的算法
?? O(n!): 求具有N個(gè)元素的全排列的算法

優(yōu)<---------------------------<劣

O(1)2n)<O(n)<O(n²)<O(2ⁿ)

排序法

?	最差時(shí)間分析	平均時(shí)間復(fù)雜度	穩(wěn)定度	空間復(fù)雜度
冒泡排序	O(n2)	O(n2)	穩(wěn)定	O(1)
快速排序	O(n2)	O(n*log2n)	不穩(wěn)定	O(log2n)~O(n)
選擇排序	O(n2)	O(n2)	穩(wěn)定	O(1)
二叉樹排序	O(n2)	O(n*log2n)	不一頂	O(n)
插入排序	O(n2)	O(n2)	穩(wěn)定	O(1)
堆排序	O(n*log2n)	O(n*log2n)	不穩(wěn)定	O(1)
希爾排序	O	O	不穩(wěn)定	O(1)

?

轉(zhuǎn)載于:https://www.cnblogs.com/hiwoshixiaoyu/p/10035074.html

總結(jié)

以上是生活随笔為你收集整理的读书笔记-《大话数据结构》第二章算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。