教材學(xué)習(xí)內(nèi)容總結(jié)

概述

• 軟件工程：是一門關(guān)于高質(zhì)量軟件開發(fā)的技術(shù)和理論的學(xué)科，用來控制開發(fā)過程，實(shí)現(xiàn)高質(zhì)量的軟件。

• 軟件工程的目標(biāo)：正確性、可靠性、健壯性、可用性、可維護(hù)性、可重用性、可移植性、運(yùn)行效率。
  對(duì)于可靠性和健壯性這兩個(gè)較難區(qū)分的特征我的理解是：可靠性可以看做一個(gè)人容易不容易生病，健壯性可以看成一個(gè)人生病后恢復(fù)的難易程度，是身體強(qiáng)壯康復(fù)快還是落下病根罒ω罒

• 程序=數(shù)據(jù)結(jié)構(gòu)+算法 ；軟件=程序+軟件工程
• 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

• 常用的數(shù)據(jù)結(jié)構(gòu)比如棧（先入后出）和隊(duì)列（先入先出）

算法分析

• 算法分析：是對(duì)一個(gè)算法需要多少計(jì)算時(shí)間和存儲(chǔ)空間作定量的分析。算法是解題的步驟，可以把算法定義成解一確定類問題的任意一種特殊的方法。算法分析是計(jì)算機(jī)科學(xué)的一個(gè)基礎(chǔ)，并涉及多種技術(shù)和概念。
• 算法效率：算法效率是指算法執(zhí)行的時(shí)間，算法執(zhí)行時(shí)間需通過依據(jù)該算法編制的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間來度量，通常是CPU的使用時(shí)間。
• 增長函數(shù)：表示問題（n）大小與我們希望最優(yōu)化的值之間的關(guān)系。該函數(shù)表示了該算法的時(shí)間復(fù)雜度（CPU的使用時(shí)間）或空間復(fù)雜度（內(nèi)存空間）。
• 漸進(jìn)復(fù)雜度（隨著n增加時(shí)增長函數(shù)的一般性質(zhì)）稱為算法的階次。算法的階次是忽略該算法的增長函數(shù)中的常量和其他次要項(xiàng)，只保留主項(xiàng)而得出的。
• 大O記法/O()：與問題大小無關(guān)、執(zhí)行時(shí)間恒定的增長函數(shù)稱為具有O（1）的復(fù)雜度。
• 具有相同階次的算法，從運(yùn)行效率的角度來說都認(rèn)為是等價(jià)的。
• 更快的CPU只能給函數(shù)增加常量，增加的值是固定的，而算法分析可以隨著函數(shù)的變化提高增值，所以不能通過提高處理器速度來替代算法分析。
• 增長函數(shù)的比較：

  • n相對(duì)較小時(shí)各種增長函數(shù)的比較
    

  • n很大時(shí)，各種增長函數(shù)的比較
    

• 循環(huán)運(yùn)行的時(shí)間復(fù)雜度分析：循環(huán)體的階次n乘以該循環(huán)要運(yùn)行的次數(shù)。
  • 例1:時(shí)間復(fù)雜度為n * O(1) = O（n）
  for(int count=0;count<n;count++) {/*復(fù)雜度為O（1）的步驟系列*/ }
  • 例2:時(shí)間復(fù)雜度為O（log2(n))；進(jìn)行次數(shù)為x，所以2^x=n,x=log2(n)，復(fù)雜度為O（1），所以為O（log2(n))
  count=1 while(count<n) {count *=2/*復(fù)雜度為O（1）的步驟系列*// }
• 嵌套循環(huán)的復(fù)雜度分析
  • 例1：內(nèi)層復(fù)雜度為O（n），外層為O（n）,故為O（n^2）
  for{int count=0;count<n;count++) {for(int count2=0;count2<n;count2++){/*復(fù)雜度為O（1）的步驟系列*/} }
• 方法調(diào)用的復(fù)雜度分析
  • 例1：復(fù)雜度為printsum方法的復(fù)雜度乘以該循環(huán)的運(yùn)行次數(shù)，即為O(n)*O(n)=O(n^2)
    printsum方法為
  for (int count=0 ; count<n; count++) {Printsum(count); } public void printsum（int count） { int sum =0; for(int i=0; i<count; i++)sum += i; System.out.println(sum); }
  • 例2：增長函數(shù)為復(fù)雜度相加，f(n)=1+n+n^2;得出時(shí)間復(fù)雜度為O（n^2）
  public void sample (int n) {printsum(n); //該方法調(diào)用復(fù)雜度為O（1）for(int count =0;count<n;count++) //該循環(huán)復(fù)雜度為O（n)printsum(count);for(int count =0;count<n;count++) //該循環(huán)復(fù)雜度為O（n^2)for(int count2 =0;count2<n;count2++)System.out.println(count,count2); }

作業(yè)解答

• EX2.1求階次

  • a.10n^2+100n+1000

    解：階次是n^2。式子中漸進(jìn)復(fù)雜度最高的是n^2,它的增長速度最快。

  • b.10n^3-7

    解：增長速度最快的是n^3

  • c. 2^n+100n^3

    解：2^n的增長速度大于n^3，所以階次是2^n

  • d. n^2logn

    解：由于是相乘，所以為原式n^2logn

• EX2.4

  for(int count = 0 ; count < n ; count++)for(int count2 = 0 ; count2 < n ; count2 = count2 + 2){System.out.println(count,count2);} }

  解：外層循環(huán)進(jìn)行次數(shù)為n，內(nèi)層循環(huán)為1/2n，所以增長函數(shù)f(n)=n* 1/2n=1/2n^2;階次為n^2

• EX2.5

  for(int count = 0 ; count < n ; count++)for(int count2 = 1 ; count2 < n ; count2 = count2 * 2){System.out.println(count,count2);} }

  解：外層循環(huán)需要進(jìn)行次數(shù)為n，內(nèi)層循環(huán)需要進(jìn)行次數(shù)為為x,則2^x=n,x=log2(n),所以增長函數(shù)是f(n)=nlog2(n)，而階數(shù)與增長函數(shù)的最高階項(xiàng)有關(guān)，要忽略次項(xiàng)與常數(shù)項(xiàng)，階次是nlog2(n).

學(xué)習(xí)進(jìn)度條

代碼行數(shù)（新增/累積）博客量（新增/累積）學(xué)習(xí)時(shí)間（新增/累積）

積累	0/7359	3/17	30/330
第一周	0/0	1/1	8/8

結(jié)對(duì)及互評(píng)

點(diǎn)評(píng)模板：

• 博客中值得學(xué)習(xí)的或問題：
  • 20172305譚鑫的博客中課本疑難問題解決的很好，內(nèi)容全面。
  • 20172323王禹涵的博客中課本內(nèi)容總結(jié)詳實(shí)，感悟深刻。
• 基于評(píng)分標(biāo)準(zhǔn)，我給譚鑫的博客打分：7分。得分情況如下：
  • 問題加分3分
  • 感悟不假大空加1分
  • 排版精美的加1分
    -正確使用Markdown語法加1分
    -模板中的要素齊全加1分
• 基于評(píng)分標(biāo)準(zhǔn)，我給王禹涵的博客打分：5分。得分情況如下：
  • 排版精美的加1分
  • 問題加分1分
  • 感悟不假大空加1分
    -正確使用Markdown語法加1分
    -模板中的要素齊全加1分

感悟

有一段時(shí)間沒有學(xué)習(xí)了，假期有點(diǎn)點(diǎn)懈怠，突然學(xué)習(xí)兩章內(nèi)容，看了很久，感覺還沒進(jìn)入狀態(tài)比較生疏，有些概念較難分清，新的一學(xué)期仍需繼續(xù)努力，多多聯(lián)系，對(duì)課本的理解要到位，加油吧！

參考

• 數(shù)據(jù)結(jié)構(gòu)
• 算法分析

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

總結(jié)

以上是生活随笔為你收集整理的20172314 2018-2019-1《程序设计与数据结构》第一周学习总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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