




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第一章 Introduction 1.1 資料與資訊 資料 ( data ) 的定義:器具體符號表示,而能夠被計算機處理的資訊 (information) 資料強調符號本身,而資訊則強調資料所呈現出來,經過人們分析、了解並領會的事實 我們將在資料結構這門課中探討計算機系統所儲存以及處理的資料,並且學習如何組織這些資料,以及處理這些資料的方法 1.2 演算法與資料結構 演算法 (algorithm) 的定義:“在有限步驟內解決數學問題的程序。在計算機科學的領域中,演算法泛指“適合被實作為計算機程式的解題方法 演算法通常具有以下五個特性:一 輸入 (Input)二 明確性 (Definitenes
2、s)三 正確性 (Correctness)或稱 有效性 (Effectiveness)四 有限性 (Finiteness)五 輸出 (Output)例1.3 歐幾里得演算法 計算兩個自然數的最大公因數 (Greatest Common Divisor, GCD) 演算法描画如下:步驟 1. 輸入兩個自然數 A , B步驟 2. A 除以B,餘數為 R步驟 3. 假设 R 為零,則跳至步驟 5步驟 4. AB,BR,跳至步驟 2步驟 5. B 即為 GCD這些敘述符合演算法的特性:一 輸入 (Input) :兩個自然數A, B 二 明確性 (Definiteness) :以逐渐追蹤法 一步一步執
3、行敘述,不呵斥混淆 三 正確性 (Correctness) :以兩組A,B代入執行均得到正確結果四 有限性 (Finiteness) :A,B,R在第二圈以後都會愈來愈小。由於他們都是正整數,所以R終會等於零 五 輸出 (Output) :A,B 的最大公因數 R = A MOD BA BB R開 始是輸入自然數A,BR = 0 ?B為GCD結 束否 用流程圖來描画這個演算法: 1.3 程式的分析 一個好的程式,通常必須滿足以下的條件:一 正確達到目的:通常以具有代表性的多組輸入來測試驗證 二 可維護性高:程式的可維護性牽涉到編寫程式的方法和風格,以下是幾項檢驗項目: 檢驗項目一:編寫程式能否
4、符合模組化的原則,提供由上而下 (Top-Down)的了解思绪? 檢驗項目二:一切的常數變數及函式 (function) 名稱能否有意義? 檢驗項目三:一切函式的輸入、輸出及功能能否被明確地定義? 檢驗項目四:能否在適當的地方加上註解? 檢驗項目五:說明文件能否詳實完備? 三 效率高:計算程式的時間複雜度來分析效率並尋求改良之道四 記憶體需求低:在不影響效率的情況下,需求愈低愈好 計算 n 階層 ( n! ) 的函式如下: int factor( int n) int result, i ;1 result = 1 ;2 i = 1 ;3 while ( i 0 時n 0,頻率計數為 3n+3
5、次,假设 n = 0 ,頻率計數為 4次A. 單層迴圈1 for ( i = 1 ; i n ; i+) 2 result = result + 1 ; 迴圈計數器i的範圍是1n-1,因此迴圈共重複 n-1 次 簡單的數學方式: n-1總次數 1 = n-1 i=1B. 雙層迴圈、內圈固定次數 1 for ( i = 1 ; i = n ; i+)2for ( j = 1 ; i n ; j+) 3 result = result + 1 ; 外圈迴圈計數器i的範圍是 1n,內圈迴圈計數器j的範圍是 1n-1,外圈每執行1圈,內圈就會執行 n-1 圈。而外圈會執行 n 圈,因此第3行敘述共將執
6、行 n * (n-1) 次。 數學方式: n n-1 n n n 總次數 1 = ( n-1) = n 1= n2-n = n*(n-1) i=1 j=1 i=1 i=1 i=1 C. 雙層迴圈、內圈不固定次數 1 for ( i = 1 ; i = n ; i+)2for ( j = i+1 ; i 0 n n0 , f (n) c * g(n)用口語解釋為:f(n) 取Big-O符號為O( g(n),當 n 夠大的時候,g(n)相當 於是f(n)的上限 nn0f(n)c*g(n)用圖示可表達為: 5n2 + 6n + 9 O( n2 ) f( n ) = 5n2 + 6n + 9, g(
7、n ) = n2 f 函數取Big-O符號為 g函數5n2 + 6n + 9 取 Big-O 符號為 O( n2 )l 3n lgn + 9n + 10 = O( nlgn ) ,因為 nlgn 的次數比n 大,取最高次項而不計係數時,自然取到 n lgnl 9 n2 + 6nlgn + 9 = O( n2 ) ,因為n2 的次數最大,取最高次項而不計係數時,自然取到n2 19n3 + 9 n2 + 6n+ 9 = O( n3 ) ,因為n3 的次數最大,取最高次項而不計係數時,自然取到 n3常見的時間複雜度等級有:l O(1):常數級l O(lgn) :對數級l O(n) :線性級l O(nlgn)l O(n2) :平方級l O(n3) :立方級l O(2n) :指數級 它們的成長速度順序是: O(1) O(lgn) O(n) O(n lgn) O(n2) O(n3) O(2n) 假设解決同樣問題的三個程式,他們的時間複雜度分別是O(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 培训费退款协议(2025年版)
- 保安班长工作总结报告
- 做销售的工作简历模板
- 酒店评价员工的评语
- 物业供应链公司合作协议
- 《玩具》(教学设计)2024-2025学年数学一年级上册 北师大版
- 2025年河南货运从业考试试题及答案
- 点图与数-平方数(教案)-二年级上册数学沪教版
- 世界全民安全教育
- 2025年巢湖c1货运从业资格证模拟考试题
- DL∕T 5362-2018 水工沥青混凝土试验规程
- 中国产科麻醉现状及产科麻醉指南解读专家讲座
- 二年级上册心理健康教学设计-第四课 找朋友|辽大版
- JTG-D82-2009公路交通标志和标线设置规范
- DZ∕T 0248-2014 岩石地球化学测量技术规程(正式版)
- 生物农药与生物防治学智慧树知到期末考试答案章节答案2024年浙江农林大学
- 淋巴结结核的个案护理
- 基于STM32的智能扫地机器人设计
- 山东省青岛市崂山区育才学校2023-2024学年下学期奇点计划选拔考试八年级物理试卷
- 赔偿协议书工程质量问题赔偿
- 海洋农场与海洋牧场
评论
0/150
提交评论