時間：2022-12-29 02:30:01 | 來源：信息時代
時間：2022-12-29 02:30:01 來源：信息時代
計算復雜性理論 : 用數(shù)學方法研究各類問題的計算復雜性的一門學科。它研究各種可計算問題在計算過程中資源消耗情況,以及在不同計算模型下,使用不同類型資源以及不同數(shù)量資源對各類問題復雜性的本質(zhì)特性和相互關(guān)系。
在計算復雜性理論中資源主要指的是各類問題在計算過程中所占用的時間與空間資源。它與問題的計算規(guī)模n有關(guān),亦即是說,算法所需時間、空間是問題規(guī)模n的函數(shù)T(n)和S(n)。
在時間復雜性的度量中,我們一般分成為兩級,其中一級是多項式級時間算法,即T(n)呈多項式表示或是∪kO(nk),其中k為常量,另一級是指數(shù)級時間算法,T(n)呈指數(shù)表示或是∪kO(kn),其中k為常量。在這兩級中算法執(zhí)行時間有著本質(zhì)上的不同。在多項式時間算法中,計算機計算能力的提高對問題計算規(guī)?？捎忻黠@增加,而在指數(shù)時間算法中,計算機計算能力的提高對問題計算規(guī)模幾乎毫無影響。因此,我們說,凡是一問題有多項式時間算法則稱該問題是易解的,并稱它屬于P類,反之,如一問題是指數(shù)時間算法則稱該問題是難解的。尋找問題的多項式時間算法或證明該問題是難解的是計算復雜性理論中所研究的重要問題。同樣的,對空間復雜性度量也有類似情況。一般認為凡是P類問題都是現(xiàn)實計算機上可解的問題,而難解的問題則是計算機所無法可解的問題。
在計算復雜性理論中還有一個重要而著名的研究課題,它即是P=? NP問題。在求解問題中,如果問題有不確定的多項式時間算法,則稱它屬NP類,NP類中最難解的問題稱NP完全類,P類是否就等于NP類,是當代算法理論中最著名的未解決難題稱P=?NP問題。目前在理論上取得的最大成果是只要證明有一個NP完全問題屬于P類,那么一切NP類問題都將屬于P類。此結(jié)論表明可以將一般性的問題解決化解成為個別特殊的問題解決。
計算復雜性理論對計算機科學以及數(shù)據(jù)庫中的算法設計與分析起到了重大的作用。一般講,任何一個計算機或數(shù)據(jù)庫中的算法其復雜性應是P類,只有這樣才能在現(xiàn)實計算機中獲得解決。
關(guān)鍵詞：數(shù)據(jù),理論,復雜
微信公眾號
版權(quán)所有? 億企邦 1997-2022 保留一切法律許可權(quán)利。
在線咨詢