1樓：奶茶
複雜性理論是計抄
算機科學的理論基礎的核心。本書是著名電腦科學家oded goldreich的力作，書中對計算任務固有複雜性研究進行了概念性介紹，全面分析了複雜性理論的現代主題。
本書涉及複雜性理論的很多子領域（如難度放大、偽隨機性及概率證明系統等），涵蓋了np完整性、空間複雜性、隨機性和計數、偽隨機數生成器等內容，還在附錄裡面介紹了現代密碼學基礎等。
本書內容嚴謹，可讀性強，適合作為高年級本科生、研究生的教材。同時，書中展示了複雜性理論的很多子領域，也適合領域專家參考。
計算複雜性理論的簡介
2樓：阿瑟
計算複雜性理論（computational complexity theory）是計算理論的一部分，研究計算問題時所需的資源，比如時間和空間，以及如何儘可能的節省這些資源。
計算複雜性理論所研究的資源中最常見的是時間（要通過多少步才能解決問題）和空間（在解決問題時需要多少記憶體）。其他資源亦可考慮，例如在平行計算中，需要多少並行處理器才能解決問題。
時間複雜度是指在電腦科學與工程領域完成一個演算法所需要的時間，是衡量一個演算法優劣的重要引數。時間複雜度越小，說明該演算法效率越高，則該演算法越有價值。
空間複雜度是指電腦科學領域完成一個演算法所需要佔用的儲存空間，一般是輸入引數的函式。它是演算法優劣的重要度量指標，一般來說，空間複雜度越小，演算法越好。我們假設有一個圖靈機來解決某一類語言的某一問題，設有x個字（word）屬於這個問題，把x放入這個圖靈機的輸入端，這個圖靈機為解決此問題所需要的工作帶格子數總和稱為空間。
複雜度理論和可計算性理論不同，可計算性理論的重心在於問題能否解決，不管需要多少資源。而複雜性理論作為計算理論的分支，某種程度上被認為和演算法理論是一種「矛」與「盾」的關係，即演算法理論專注於設計有效的演算法，而複雜性理論專注於理解為什麼對於某類問題，不存在有效的演算法。
計算複雜性的介紹
3樓：騷b雪的桃
所謂計算複雜性，通俗說來，就是用計算機求解問題的難易程度。其度量標準：一是計算所需的步數或指令條數（這叫時間複雜度），二是計算所需的儲存單元數量（這叫空間複雜度）的書籍。
計算複雜性的發展
4樓：孤獨患者丶峎
現**論電腦科學中最重要的分支之一，它研究各種問題類在計算時所需要耗費的時間、空間等資源的多少，是可計算性理論的新發展。 什麼樣的問題類是可計算的？這是數學、數理邏輯學和早期電腦科學所關心的一個重要問題。
為了回答這個問題，可以給出一個計算的模型，然後規定，凡是這個模型能計算的問題類就叫作可計算的，否則就叫作不可計算的。於是產生了各種計算的模型：圖靈機、遞迴函式、λ 演算、馬爾可夫演算法和遞迴演算法等。
但是，會不會有一類問題，在一個模型中是可計算的，而在另一個模型中卻是不可計算的呢？如果這樣，一個問題類的可計算性就依賴於模型，而不是問題類本身的性質了。著名的丘奇－圖靈論題回答了這個問題。
這個論題說：「凡是合理的計算模型都是等價的，即一個模型能算的問題類別的模型也能算，一個模型不能算的別的模型也不能算。」這個論題不是一個嚴格的命題，無法給於一般的證明，但可以對一個個具體的模型去驗證它的正確性。
但是，對於一個問題類，只知道它能否計算還很不夠，更有實際意義的是要知道計算起來要耗費多少時間，要用多大的空間來儲存計算的中間結果等等。為了回答這些進一步的問題，就產生了計算複雜性理論。
資源計算時間、儲存大小都稱為資源。嚴格地講，每一種資源的定義都依賴於特定的計算模型。對各種計算模型，資源的定義雖不一樣，但主要的可分為三類：
① 序列時間（簡稱時間） 它是計算過程中的總運算量，即把計算分成一些原始的步驟，完成這些步驟所需要的總時間。
② 空間 它是為了儲存中間結果所需要的儲存器的大小。例如在計算時用一塊黑板來打草稿，每一單位面積假定可以寫一個符號，不用了還可以擦掉。在計算時所需黑板面積就是空間。
③ 並行時間 它是平行計算所需要的時間，亦即如果多人或多處理機協同計算，解決一個問題所需要的時間。 相似性原理所涉及的模型主要研究計算中按位運算的總量時間，按位計的中間結果儲存量空間和計算的深度（並行時間）等等，所以可稱為按位的複雜性。代數的複雜性理論則研究在一個代數系統中（例如實數域中）從給定變數出發去計算某些函式所需要的代數運算（例如加法、乘法）代數判斷（例如大於或等於）的次數（時間），所需中間變元的個數（空間），計算的深度（並行時間）等等。
在實際運算中，既不能給出一個無限長的實數，也不能在一個單位時間內完成兩個實數的乘法。真正的算術運算都是通過近似小數的按位運算得出來的。所以按位的複雜性具有更為基本的意義。
通過下面的例子，可以得到關於代數複雜性的一些感性認識。通常兩個n階矩陣相乘要做n3次數乘法，v.斯特拉森找到了一個演算法，只需做次數乘法。
此後這個上界又被許多人不斷改進到，至2023年12月，又改進為。d.科普爾史密斯和s.
維諾格拉特還證明：最好的演算法不存在，也就是說這個上界可以永遠改進下去。
計算複雜性理論的理論與實踐
演算法在最壞情況，最好情況和平均情況下的計算複雜性概念及對三者時間複雜性的分析？
5樓：匿名使用者
計算複雜性目前主要用計算所消耗的資源數量來量度。由於演算法在計算時所消耗的資源與問題規模有關，所以通常用遞增函式來估計。另外，對具體問題例項，演算法的資源消耗量是不同的，通常可以估計出最壞、最好和平均三種情形下對資源消耗的數量。
對上述三者作時間複雜性分析的具體做法如下：以順序查詢為例，最壞情況是指需要搜尋完所有的資料；最好情況是指搜尋的第一個資料就是所要的資料；平均情況是指所獲得的資料按其實際分佈而言，平均需要查詢比較的次數。
可計算性與計算複雜性講義
6樓：匿名使用者
可以看看這裡，學海網：
可計算性與計算複雜性講義
第二章 可計算函式 1
1、原語言 1
2、可計算函式 1
習 題 2
第三章 遞迴函式 3
1、運算元 3
2、原始遞迴函式 3
3、原始遞迴謂詞 3
4、受囿取極小 4
5、遞迴與可計算性 5
習 題 6
第四章 post-turing程式和turing機 81、p-t程式 8
2、turing機 9
3、p-t程式編碼 10
4、一些定理 10
習 題 11
第五章 半可計算性 17
習 題 18
第六章 半圖厄系統 19
1、半圖厄系統 19
2、半圖厄系統與圖靈機、半可計算集 19
3、不可判定問題 19
習 題 20
第七章 圖靈機 27
習 題 28
第八章 計算複雜性理論 37
習 題 38
歷 年 真 題 46
重慶大學演算法分析與計算複雜性 怎麼複習
7樓：山泉清水淌
關於複習方法，這裡給你一些思路：
1、章節複習，不管是那門學科都分為大的章節和小的課時，一般當講完一個章節的所有課時就會把整個章節串起來在系統的講一遍，作為複習，我們同樣可以這麼做，因為既然是一個章節的知識，所有的課時之前一定有關聯，因此我們可以找出它們的共同之處，採用關聯記憶法把這些零碎的知識通過線串起來，更方便我們記憶。
2、糾錯整理：做題的過程中難免會做錯題目，不管你是粗心或者就是不會，都要習慣性的把這些錯題收集起來，每個科目都建立一個錯題集，當我們進行考前複習的時候，它們是重點複習物件，因此你既然錯過一次，保不準會錯第二次，只有這樣你才不會在同樣的問題上再次失分。
3、思維導圖複習：思維導圖是一個偉大的發明，在記憶上可以讓你大腦裡的資料系統化、影象化，還可以幫助你思維分析問題，統籌規劃。將知識用思維導圖畫出來進行整理記憶，可以很快分析出知識的脈絡和重點，並且記得牢固。
真核生物比原核生物基因表達的複雜性,表現在哪些方面
真核生物比原核生物基因表達的複雜性,表現在哪些方面 1 原核生物和真核生物基 回因表達調控的共同點答 a 結構基因均有調控序列 b 表達過程都具有複雜性,表現為多環節 c 表達的時空性,表現為不同發育階段和不同組織器官上的表達的複雜性。2 與原核生物比較,真核生物基因表達調控具有自己的特點 a 真核...
什麼是c語言中的時間複雜度如何計算
時間復抄雜度不是相對於襲 程式而言的,而是指問題的複雜 例如排序,對分查詢在最劣情況下也是平方問題,但對於絕大多數問題而言,我們只關心平均效率。例如稀疏陣列,可以降低對空間的要求,但當有用資料超過一定規模,執行速度將急劇下降。次數超過4的多項式沒有平凡解,所以被成為大o的n次方問題,這樣的問題總是需...
想法比普通人的想法還要複雜,這種人有什麼性格
其實當你可以去把自己的想法變得簡單一點點,那麼自己就不會那麼複雜了,有的時候複雜是因為你把自己的想法變得複雜了,而且你需要學會去讓自己堅強起來的 那得看他的三觀,但可以肯定的是他是個聰明人 為什麼有的人愛研究心理,這種人一般是什麼性格的人?因為發呆是世界上最舒服的事啊,發呆時我們可以排開一切,忘記煩...