如果f(n)=o(s(n))並且g(n)=o(r(n)),則f(n)+g(n)=o(s(n)+r(n))
如果f(n)=o(s(n))並且g(n)=o(r(n)),則f(n)*g(n)=o(s(n)*r(n))
根據符號o的定義，存在正常數c1，c2和自然數n1,n2，使得對所有的n>= n1，f（n）<=c1s(n)；對所有的n>= n2,g(n) <=c2r(n)所以 f（n）+ g(n) <= c1s(n)+ c2r(n)，f（n）*g(n)<= c1c2s(n)r(n)；令 c3=max（c1,c2），c4=c1*c2；
則：f（n）+ g(n) <= c3[s(n)+ r(n)]=o(s(n)+ r(n))
f（n）*g(n) <= c4*s(n)*r(n)=o(s(n)* r(n))
試說明為什麼「在現代計算機上執行指數（如2n）時間演算法是不可能的，要想在順序處理機上擴大所處理問題的規模，有效的途徑是降低演算法計算複雜度的數量級，而不是提高計算機的速度」。
乙個計算時間為ο(1)的演算法，它的基本運算執行的次數是固定的，因此，總的時間由乙個常數(即零次多項式)來限界，而乙個時間為ο(n2)的演算法則由乙個二次多項式來限界。當資料集的規模（即n的取值）很大時，要在現代計算機上執行具有比o（nlog2 n）複雜度還高的演算法是很困難的，尤其是指數時間演算法，它只有在在n值取得非常小的時候才實用。例：
假設解決同乙個問題的兩個演算法，它們都有n個輸入，計算時間的數量級分別是n^2和nlogn.則n=1024，分別需要1048576和10240次運算。n=2048：
分別需要4194304和22528次運算。由此，在n加倍的情況下，乙個o（n^2)的演算法計算時間增長4倍，而乙個o（nlogn）演算法則只用兩倍多一點的時間。所以數量級的大小對演算法的有效性有決定性的影響。
儘管通過提高計算機的速度比之前快1000倍，甚至10000倍，但當指數規模的n足夠大時，n每增加1，1000倍的提速即可瞬間化為烏有。
1、什麼是電腦科學中所說的「演算法（algorithm
演算法是一種描述程式行為的語言，是滿足下述性質的指令序列。
有限性：每條指令的執行次數、時間有限
確定性：每條指令有確定的含義、無歧義
輸入：0個或多個輸入
輸出：1個或多個輸出
2、滿足何種性質的問題被稱為稱為np完全問題？請簡述研究np完全問題的意義；
（1）np即是多項式複雜程度的非確定性問題。 而如果任何乙個np問題都能通過乙個多項式時間演算法轉換為某個np問題，那麼這個np問題就稱為np完全問題。如果乙個np完全問題能在多項式時間內得到解決，那麼np中的每乙個問題都可以在多項式時間內解決。
（2）它可以在多項式時間內求解，當且僅當所有的其他的np－完全問題也可以在多項式時間內求解。這樣一來,只要我們找到乙個npc問題的多項式解,所有的np問題都可以多項式時間內劃歸成這個npc問題,再用多項式時間解決,這樣np就等於p了.知道乙個問題是np完全的就給我們提供了有價值的資訊，告訴我們採用什麼樣的途徑可以是最富有成效的。
簡言之，np完全性理論的初步應用是幫助演算法設計人員找到最有可能得到有用的演算法的努力方向
3、「當問題的最優解包含了其子問題的最優解時，稱該問題具有最優子結構性質」。問題的最優子結構性質是該問題可用動態規劃演算法求解的基本要素，試簡要闡述「論證某一問題的最優子結構性質」時的一般方法；
矩陣連乘計算次序問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質。首先假設由問題的最優解匯出的子問題的解不是最優的，然後再設法說明在這個假設下可構造出比原問題最優解更好的解，從而導致矛盾。
利用問題的最優子結構性質，以自底向上的方式遞迴地從子問題的最優解逐步構造出整個問題的最優解。最優子結構是問題能用動態規劃演算法求解的前提。
1、棋盤覆蓋問題
2、使用乙個快速排序的迭代模型可以使原遞迴演算法所需的棧空間總量減至o（logn）。試設計這一迭代模型（演算法）。（18分）
3、社會名流問題
給定乙個n×n鄰接矩陣，確定是否存在乙個i，其滿足在第i列所有項（除了第ii項）都為1，並且第i行所有項（除了第ii項）都為0。大致的演算法思路：隨便取乙個非對角線元素比如array[i][j]，如果array[i][j]=0成立，則j不是社會名流，於是刪去第j行和第j列。
同樣，如果array[i][j]=1成立，則刪去第i行和第i列；總之，無論對應項取何值，都可以刪去一行和一列，因此整個操作只耗費o(n)的時間。重複此操作直至剩下最後乙個元素。最後，檢驗該元素是否為社會名流即可。
如果該元素不是，則該群人中不存在社會名流。
補充： 1假設某演算法在輸入規模為n時的計算時間為：t（n）=3*2n ，在a型計算機上實現並完成該演算法的時間為t秒，現有更先進的b型計算機，其運算速度為a型計算機的64倍。
試求出若在先進的b型機上執行同一演算法在則t秒內能求解輸入規模為多大的問題？某台t秒內完成的基本運算的次數=3*2^n新機器t秒內完成的基本運算的次數=64*3*2^n=2^6*3*2^n=3*2^(n+6)
設n為b型機上t秒鐘能求解的問題的規模
所以t=t(n)=3*2^n=3*2^(n+6) 則：n=n+6
4. 試說明如何修改快速排序演算法，使它在最壞情況下的計算時間為o(nlgn)。
可以通過減少遞迴棧的使用進行優化，快速排序的實現需要消耗遞迴棧的空間，而大多數情況下都會通過使用系統遞迴棧來完成遞迴求解。對系統棧的頻繁訪問會影響到排序的效率。在資料量較大時，快速排序的複雜度為o(nlgn)。
當資料集較小時，快排的複雜度有向o(n^2)發展的趨勢，此時不必繼續遞迴呼叫快速排序演算法，使用插入排序代替快速排序。stl中sort就是用的快排+插入排序的，使得最壞情況下的時間複雜度也是o(nlgn)．這一改進被證明比持續使用快速排序演算法要有效的多。
5. 試設計乙個構造連通圖g生成樹的演算法，使得構造出的生成樹的邊的最大權值達到最小。
解答：可以證明，圖g的最小生成樹即為滿足題意的生成樹。假設t，t』分別為圖g的最小生成樹及邊的最大權值達到最小值的生成樹。
v，v』分別為它們的最大權邊。假如w(v)>w(v』),則將v從t刪除之後，t變為兩個連同的分支，此時，一定有t』的邊v1連同這兩個分支，否則t』將是不連通的。從而將v1加入到t中構成一新的生成樹t』』=t-v+v1。
且有w(v1)1證明0-1揹包問題滿足最優子結構性質
假設第k個物品是最優解中的乙個物品，則從中拿出wk對應的物品後所對應的解一定是其餘n-1個物品，裝入揹包最大承載重量為c-wk的最優解，否則與假設矛盾。
2對計算複雜性的研究能夠使人們弄清所求解問題的固有難度，並得出評價某類演算法優劣的準則，用以指導設計出更高效的演算法。試用簡短的語言說明「建立乙個問題複雜性的下界要比確定它的上界困難得多！」其複雜性上界是已知求解該問題的最快演算法的費用，而複雜性下界只能通過理論證明來建立。
尋求某個問題的計算複雜性上界，只要研究乙個演算法的複雜性即可。但是要尋求同一問題的計算複雜性下界，則必須考察所有的解決該問題的演算法，證明乙個問題的複雜性下界就需要證明不存在任何複雜性低於下界的演算法。顯然，建立下界要比確定上界困難得多。
1. 最大值和最小值問題的最優演算法：給定n個實數存放於一維陣列a中，試設計乙個演算法在最壞情況下用3n/2-2次的比較找出a中的最大值和最小值
6. 試設計在o(n)時間內求得陣列a[1..n]的中位數的演算法。
將n個輸入元素劃分成n/5(上取整)個組，每組5個元素，只可能有乙個組不是5個元素。用任意一種排序演算法，將每組中的元素排好序，並取出每組的中位數，共n/5(上取整) 個。找出這n/5(上取整)個元素的中位數。
如果n/5(上取整)是偶數，就找它的2個中位數中較大的乙個。
第1行測試：如果i=n，表示已經搜尋到了葉節點。
如果從x[n-1]到x[n]以及從x[n]到起點x[1]有一條邊，則找到了一條迴路。
此時，第3行需要判斷該迴路是否是目前發現的最優迴路。如果是，第4行-6行則更新迴路的權和bestw以及最優迴路。第7-13行繼續回溯，在第8行，如果從x[i-1]到x[j]有一條邊，且b(i)小於當前最優解的值bestw，則表示可以繼續往下搜尋，同時更新目前所構造路徑的權值cw。
證明乙個問題具有貪心選擇性質的一般方法
令子問題sij≠且a1為子問題sij中的最優解，則a1一定包含在子問題sij中某個任務相互相容的最大子集中。
tsp問題
此問題相當於在乙個有向賦權圖中尋找乙個最短的哈密頓迴路。
- - ：第i個頂點，假設推銷員從第0號點出發，呼叫s時就要傳入
v：從出發，要到達的頂點的集合
：從出發，經過v中各點，並僅經過一次後，回到所需的最短路徑長度（若與目標點不直接連通，則記其路程為無窮大）
：點i到j的距離
廣義揹包問題（從最大遞迴，決定每個放不放，價值增不增加）
i：（第）i種物品；
j：揹包中剩餘載重量；
m（i,j）：當揹包內剩餘載重量為j，考慮對於前i種物品的裝入方案時，得到的最大物品價值
：第i種物品的重量 ：第i種物品的價值
證明f(n) – g(n) != o(s(n) – r(n))
設f(n) = n^2+n g(n) = n^2 有f(n) – g(n) = n ;o(s(n) – r(n)) = 0不相等
北京工業大學電子課程設計報告
學院專業班級組號 題目1 2 姓名學號 指導教師 成績年月日 數字部分 自行車里程表 設計 製作乙個根據車輪周長 輻條數等引數來記錄行駛里程的簡易里程表。要求具有可調整的手段，以適應不同車型。首先使用紅外光電感測器對轉動的車輪輻條進行測量，產生計數脈衝。若以0.1公里作為里程表的計數單位，則需測量出...
北京工業大學研究生開題報告
學位級別 博士 碩士 工程碩士 mba學號研究生姓名 指導教師姓名 專業名稱 所在學院 開題報告時間 北京工業大學研究生部製表 注意 本表基本情況及報告正文由研究生本人填寫，碩士不少於，博士不少於。格式要求 正文文字部分為5號宋體 單倍行間距排版，a4紙雙面列印裝訂。開題報告評價部分分別由指導教師及...
北京工業大學電子工程設計報告第一階
電子工程設計報告 題目 穩壓電源與變送器電路設計 專業 電子資訊工程 小組 14組 姓名學號 09024129 09024126 指導老師 司農 完成日期 2009，10 摘要 電子工程設計訓練是一門新開的實踐教學課程，其宗旨是以課堂教學的形式，根據訓練內容，提出功能和指標，通過訓練，培養每乙個學生...