① 求解：為什麼演算法執行時間和所佔存儲空間的耗費兩者之間是矛盾的又為什麼以演算法執行時間作為演算法優劣的
主要是由於實際數學運算與計算機的運算指令有差異，很多運算要轉化成相應的計算機運算指令，就牽扯到運算的進一步分解和排序。很顯然，這個分解的邏輯越簡單，所用的指令就會越小，但是要達到預期計算目的就需要重復更多次；如果把邏輯搞得比較復雜，佔用的指令就會越多，但是要達到預期計算目的可能只需要簡單重復幾次。
打個比方：搬磚。你要搬100塊磚，如果一次搬20塊（佔用空間大），只需5次就能搬完（執行時間短）；如果一次搬5塊（佔用空間小），需要搬20次（執行時間長）。
當然，上述論述都是基於這個演算法採用不同實現後工作總量差異不大的前提。現實情況下，演算法進行合理優化能夠極大降低工作總量。還是上面的搬磚，優化之後我花搬5塊的力氣就能搬20塊，5次搬完……
② 一個演算法的空間復雜度是O(1)，那麼執行該演算法時不需要任何空間，這個說法正確嗎為什麼
不正確，執行該演算法時需要空間
O(1)表示該程序所佔用的空間和所用數據量無關。
空間復雜度是對一個演算法在運行過程中臨時佔用存儲空間大小的量度。
如當一個演算法的空間復雜度為一個常量，即不隨被處理數據量n的大小而改變時，可表示為O(1)
③ 二級c公共基礎知識
第一章 數據結構與演算法
經過對部分考生的調查以及對近年真題的總結分析，筆試部分經常考查的是演算法復雜度、數據結構的概念、棧、二叉樹的遍歷、二分法查找，讀者應對此部分進行重點學習。
詳細重點學習知識點：
1．演算法的概念、演算法時間復雜度及空間復雜度的概念
2．數據結構的定義、數據邏輯結構及物理結構的定義
3．棧的定義及其運算、線性鏈表的存儲方式
4．樹與二叉樹的概念、二叉樹的基本性質、完全二叉樹的概念、二叉樹的遍歷
5．二分查找法
6．冒泡排序法
1.1演算法
考點1 演算法的基本概念
考試鏈接：
考點1在筆試考試中考核的幾率為30%，主要是以填空題的形式出現，分值為2分，此考點為識記內容，讀者還應該了解演算法中對數據的基本運算。
計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
1．演算法的基本特徵：可行性、確定性、有窮性、擁有足夠的情報。
2．演算法的基本要素：
（1）演算法中對數據的運算和操作
一個演算法由兩種基本要素組成：一是對數據對象的運算和操作；二是演算法的控制結構。
在一般的計算機系統中，基本的運算和操作有以下4類：算術運算、邏輯運算、關系運算和數據傳輸。
（2）演算法的控制結構：演算法中各操作之間的執行順序稱為演算法的控制結構。
描述演算法的工具通常有傳統流程圖、N-S結構化流程圖、演算法描述語言等。一個演算法一般都可以用順序、選擇、循環3種基本控制結構組合而成。
考點2 演算法復雜度
考試鏈接：
考點2在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為重點識記內容，讀者還應該識記演算法時間復雜度及空間復雜度的概念。
1.演算法的時間復雜度
演算法的時間復雜度是指執行演算法所需要的計算工作量。
同一個演算法用不同的語言實現，或者用不同的編譯程序進行編譯，或者在不同的計算機上運行，效率均不同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為一個特定演算法"運行工作量"的大小，只依賴於問題的規模（通常用整數n表示），它是問題規模的函數。即
演算法的工作量=f（n）
2.演算法的空間復雜度
演算法的空間復雜度是指執行這個演算法所需要的內存空間。
一個演算法所佔用的存儲空間包括演算法程序所佔的空間、輸入的初始數據所佔的存儲空間以及演算法執行過程中所需要的額外空間。其中額外空間包括演算法程序執行過程中的工作單元以及某種數據結構所需要的附加存儲空間。如果額外空間量相對於問題規模來說是常數，則稱該演算法是原地工作的。在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術，以便盡量減少不必要的額外空間。
疑難解答：演算法的工作量用什麼來計算？
演算法的工作量用演算法所執行的基本運算次數來計算，而演算法所執行的基本運算次數是問題規模的函數，即演算法的工作量=f（n），其中n是問題的規模。
1.2數據結構的基本概念
考點3 數據結構的定義
考試鏈接：
考點3在筆試考試中，是一個經常考查的內容，在筆試考試中出現的幾率為70%，主要是以選擇的形式出現，分值為2分，此考點為識記內容，讀者還應該識記數據的邏輯結構和存儲結構的概念。
數據結構作為計算機的一門學科，主要研究和討論以下三個方面：
（1）數據集合中個數據元素之間所固有的邏輯關系，即數據的邏輯結構；
（2）在對數據元素進行處理時，各數據元素在計算機中的存儲關系，即數據的存儲結構；
（3）對各種數據結構進行的運算。
數據：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中並被計算機程序處理的符號的總稱。
數據元素：是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。
數據對象：是性質相同的數據元素的集合，是數據的一個子集。
數據的邏輯結構是對數據元素之間的邏輯關系的描述，它可以用一個數據元素的集合和定義在此集合中的若干關系來表示。數據的邏輯結構有兩個要素：一是數據元素的集合，通常記為D；二是D上的關系，它反映了數據元素之間的前後件關系，通常記為R。一個數據結構可以表示成
B=（D，R）
其中B表示數據結構。為了反映D中各數據元素之間的前後件關系，一般用二元組來表示。
數據的邏輯結構在計算機存儲空間中的存放形式稱為數據的存儲結構（也稱數據的物理結構）。
由於數據元素在計算機存儲空間中的位置關系可能與邏輯關系不同，因此，為了表示存放在計算機存儲空間中的各數據元素之間的邏輯關系（即前後件關系），在數據的存儲結構中，不僅要存放各數據元素的信息，還需要存放各數據元素之間的前後件關系的信息。
一種數據的邏輯結構根據需要可以表示成多種存儲結構，常用的存儲結構有順序、鏈接、索引等存儲結構。而採用不同的存儲結構，其數據處理的效率是不同的。因此，在進行數據處理時，選擇合適的存儲結構是很重要的。
考點4 線性結構與非線性結構
考試鏈接：
考點4在筆試考試中，雖然說不是考試經常考查的內容，但讀者還是對此考點有所了解，在筆試考試中出現的幾率為30%，主要是以填空題出現的形式出現，分值為2分，此考點為識記內容。
根據數據結構中各數據元素之間前後件關系的復雜程度，一般將數據結構分為兩大類型：線性結構與非線性結構。如果一個非空的數據結構滿足下列兩個條件：
（1）有且只有一個根結點；
（2）每一個結點最多有一個前件，也最多有一個後件。
則稱該數據結構為線性結構。線性結構又稱線性表。在一個線性結構中插入或刪除任何一個結點後還應是線性結構。如果一個數據結構不是線性結構，則稱之為非線性結構。
疑難解答：空的數據結構是線性結構還是非線性結構？
一個空的數據結構究竟是屬於線性結構還是屬於非線性結構，這要根據具體情況來確定。如果對該數據結構的演算法是按線性結構的規則來處理的，則屬於線性結構；否則屬於非線性結構。
1.3棧及線性鏈表
考點5 棧及其基本運算
考試鏈接：
考點5在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，分值為2分，此考點為重點掌握內容，讀者應該掌握棧的運算 。
1．棧的基本概念
棧是限定只在一端進行插入與刪除的線性表，通常稱插入、刪除的這一端為棧頂，另一端為棧底。當表中沒有元素時稱為空棧。棧頂元素總是後被插入的元素，從而也是最先被刪除的元素；棧底元素總是最先被插入的元素，從而也是最後才能被刪除的元素。棧是按照"先進後出"或"後進先出"的原則組織數據的。
2．棧的順序存儲及其運算
用一維數組S（1∶m）作為棧的順序存儲空間，其中m為最大容量。
在棧的順序存儲空間S（1∶m）中，S（bottom）為棧底元素，S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。
棧的基本運算有三種：入棧、退棧與讀棧頂元素。
（1）入棧運算：入棧運算是指在棧頂位置插入一個新元素。首先將棧頂指針加一（即top加1），然後將新元素插入到棧頂指針指向的位置。當棧頂指針已經指向存儲空間的最後一個位置時，說明棧空間已滿，不可能再進行入棧操作。這種情況稱為棧"上溢"錯誤。
（2）退棧運算：退棧是指取出棧頂元素並賦給一個指定的變數。首先將棧頂元素（棧頂指針指向的元素）賦給一個指定的變數，然後將棧頂指針減一（即top減1）。當棧頂指針為0時，說明棧空，不可進行退棧操作。這種情況稱為棧的"下溢"錯誤。
（3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個指定的變數。這個運算不刪除棧頂元素，只是將它賦給一個變數，因此棧頂指針不會改變。當棧頂指針為0時，說明棧空，讀不到棧頂元素。
小技巧：棧是按照"先進後出"或"後進先出"的原則組織數據，但是出棧方式有多種選擇，在考題中經常考查各種不同的出棧方式。
考點6 線性鏈表的基本概念
考試鏈接：
考點6在筆試考試中出現的幾率為30%，主要是以選擇的形式出現，分值為2分，此考點為識記內容。重點識記結點的組成。
在鏈式存儲方式中，要求每個結點由兩部分組成：一部分用於存放數據元素值，稱為數據域，另一部分用於存放指針，稱為指針域。其中指針用於指向該結點的前一個或後一個結點（即前件或後件）。
鏈式存儲方式既可用於表示線性結構，也可用於表示非線性結構。
（1）線性鏈表
線性表的鏈式存儲結構稱為線性鏈表。
在某些應用中，對線性鏈表中的每個結點設置兩個指針，一個稱為左指針，用以指向其前件結點；另一個稱為右指針，用以指向其後件結點。這樣的表稱為雙向鏈表。
（2）帶鏈的棧
棧也是線性表，也可以採用鏈式存儲結構。帶鏈的棧可以用來收集計算機存儲空間中所有空閑的存儲結點，這種帶鏈的棧稱為可利用棧。
疑難解答：在鏈式結構中，存儲空間位置關系與邏輯關系是什麼？
在鏈式存儲結構中，存儲數據結構的存儲空間可以不連續，各數據結點的存儲順序與數據元素之間的邏輯關系可以不一致，而數據元素之間的邏輯關系是由指針域來確定的。
1.4樹與二叉樹
考點7 樹與二叉樹及其基本性質
考試鏈接：
考點7在筆試考試中，是一個必考的內容，在筆試考試中出現的幾率為100%，主要是以選擇的形式出現，有時也有出現在填空題中，分值為2分，此考點為重點掌握內容。重點識記樹及二叉樹的性質。
誤區警示：
滿二叉樹也是完全二叉樹，而完全二叉樹一般不是滿二叉樹。應該注意二者的區別。
1、樹的基本概念
樹(tree）是一種簡單的非線性結構。在樹結構中，每一個結點只有一個前件，稱為父結點，沒有前件的結點只有一個，稱為樹的根結點。每一個結點可以有多個後件，它們稱為該結點的子結點。沒有後件的結點稱為葉子結點。
在樹結構中，一個結點所擁有的後件個數稱為該結點的度。葉子結點的度為0。在樹中，所有結點中的最大的度稱為樹的度。
2、二叉樹及其基本性質
（1）二叉樹的定義
二叉樹是一種很有用的非線性結構，具有以下兩個特點：
①非空二叉樹只有一個根結點；
②每一個結點最多有兩棵子樹，且分別稱為該結點的左子樹和右子樹。
由以上特點可以看出，在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。另外，二叉樹中的每個結點的子樹被明顯地分為左子樹和右子樹。在二叉樹中，一個結點可以只有左子樹而沒有右子樹，也可以只有右子樹而沒有左子樹。當一個結點既沒有左子樹也沒有右子樹時，該結點即為葉子結點。
（2）二叉樹的基本性質
二叉樹具有以下幾個性質：
性質1：在二叉樹的第k層上，最多有2k-1（k≥1）個結點；
性質2：深度為m的二叉樹最多有2m-1個結點；
性質3：在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一個。
性質4：具有n個結點的二叉樹，其深度至少為〔log2n〕+1，其中〔log2n〕表示取log2n的整數部分。
小技巧：在二叉樹的遍歷中，無論是前序遍歷，中序遍歷還是後序遍歷，二叉樹的葉子結點的先後順序都是不變的。
3、滿二叉樹與完全二叉樹
滿二叉樹是指這樣的一種二叉樹：除最後一層外，每一層上的所有結點都有兩個子結點。在滿二叉樹中，每一層上的結點數都達到最大值，即在滿二叉樹的第k層上有2k-1個結點，且深度為m的滿二叉樹有2m－1個結點。
完全二叉樹是指這樣的二叉樹：除最後一層外，每一層上的結點數均達到最大值；在最後一層上只缺少右邊的若干結點。
對於完全二叉樹來說，葉子結點只可能在層次最大的兩層上出現：對於任何一個結點，若其右分支下的子孫結點的最大層次為p，則其左分支下的子孫結點的最大層次或為p，或為p+1。
完全二叉樹具有以下兩個性質：
性質5:具有n個結點的完全二叉樹的深度為〔log2n〕+1。
性質6:設完全二叉樹共有n個結點。如果從根結點開始，按層次（每一層從左到右）用自然數1，2，……，n給結點進行編號，則對於編號為k（k=1，2，……，n）的結點有以下結論：
①若k=1，則該結點為根結點，它沒有父結點；若k>1，則該結點的父結點編號為INT（k/2）。
②若2k≤n，則編號為k的結點的左子結點編號為2k；否則該結點無左子結點（顯然也沒有右子結點）。
③若2k+1≤n，則編號為k的結點的右子結點編號為2k+1；否則該結點無右子結點。
考點8 二叉樹的遍歷
考試鏈接：
考點8在筆試考試中考核幾率為30%，分值為2分，讀者應該熟練掌握各種遍歷的具體演算法，能由兩種遍歷的結果推導另一種遍歷的結果。
在遍歷二叉樹的過程中，一般先遍歷左子樹，再遍歷右子樹。在先左後右的原則下，根據訪問根結點的次序，二叉樹的遍歷分為三類：前序遍歷、中序遍歷和後序遍歷。
（1）前序遍歷：先訪問根結點、然後遍歷左子樹，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹。
（2）中序遍歷：先遍歷左子樹、然後訪問根結點，最後遍歷右子樹；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後訪問根結點，最後遍歷右子樹。
（3）後序遍歷：先遍歷左子樹、然後遍歷右子樹，最後訪問根結點；並且，在遍歷左、右子樹時，仍然先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。
疑難解答：樹與二叉樹的不同之處是什麼？
在二叉樹中，每一個結點的度最大為2，即所有子樹（左子樹或右子樹）也均為二叉樹，而樹結構中的每一個結點的度可以是任意的。
1.5查找技術
考點9 順序查找
考試鏈接：
考點9在筆試考試中考核幾率在30%，一般出現選擇題中，分值為2分，讀者應該具體掌握順序查找的演算法。
查找是指在一個給定的數據結構中查找某個指定的元素。從線性表的第一個元素開始，依次將線性表中的元素與被查找的元素相比較，若相等則表示查找成功；若線性表中所有的元素都與被查找元素進行了比較但都不相等，則表示查找失敗。
在下列兩種情況下也只能採用順序查找：
（1）如果線性表為無序表，則不管是順序存儲結構還是鏈式存儲結構，只能用順序查找。
（2）即使是有序線性表，如果採用鏈式存儲結構，也只能用順序查找。
考點10 二分法查找
考試鏈接：
考點10在筆試考試中考核幾率為30%，一般出現填空題中，分值為2分，考核比較多查找的比較次數，讀者應該具體掌握二分查找法的演算法。
二分法只適用於順序存儲的，按非遞減排列的有序表，其方法如下：
設有序線性表的長度為n，被查找的元素為i，
（1）將i與線性表的中間項進行比較；
（2）若i與中間項的值相等，則查找成功；
（3）若i小於中間項，則在線性表的前半部分以相同的方法查找；
（4）若i大於中間項，則在線性表的後半部分以相同的方法查找。
疑難解答：二分查找法適用於哪種情況？
二分查找法只適用於順序存儲的有序表。在此所說的有序表是指線性表中的元素按值非遞減排列（即從小到大，但允許相鄰元素值相等）。
這個過程一直進行到查找成功或子表長度為0為止。
對於長度為n的有序線性表，在最壞情況下，二分查找只需要比較log2n次。
1.6排序技術
考點11 交換類排序法
考試鏈接:
考點11屬於比較難的內容，一般以選擇題的形式考查，考核幾率為30%，分值約為2分，讀者應該熟練掌握幾種排序演算法的基本過程。
冒泡排序法和快速排序法都屬於交換類排序法。
（1）冒泡排序法
首先，從表頭開始往後掃描線性表，逐次比較相鄰兩個元素的大小，若前面的元素大於後面的元素，則將它們互換，不斷地將兩個相鄰元素中的大者往後移動，最後最大者到了線性表的最後。
然後，從後到前掃描剩下的線性表，逐次比較相鄰兩個元素的大小，若後面的元素小於前面的元素，則將它們互換，不斷地將兩個相鄰元素中的小者往前移動，最後最小者到了線性表的最前面。
對剩下的線性表重復上述過程，直到剩下的線性表變空為止，此時已經排好序。
在最壞的情況下，冒泡排序需要比較次數為n（n－1）/2。
（2）快速排序法
它的基本思想是：任取待排序序列中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子序列，左子序列元素的排序碼均小於或等於基準元素的排序碼，右子序列的排序碼則大於基準元素的排序碼，然後分別對兩個子序列繼續進行排序，直至整個序列有序。
疑難解答：冒泡排序和快速排序的平均執行時間分別是多少？
冒泡排序法的平均執行時間是O（n2），而快速排序法的平均執行時間是O（nlog2n）。
1.7 例題詳解
一、選擇題
【例1】演算法的時間復雜度取決於_______。（考點2）
A）問題的規模 B）待處理的數據的初態
C）問題的難度 D）A）和B）
解析：演算法的時間復雜度不僅與問題的規模有關，在同一個問題規模下，而且與輸入數據有關。即與輸入數據所有的可能取值范圍、輸入各種數據或數據集的概率有關。
答案：D）
【例2】在數據結構中，從邏輯上可以把數據結構分成_______。（考點3）
A）內部結構和外部結構 B）線性結構和非線性結構
C）緊湊結構和非緊湊結構 D）動態結構和靜態結構
解析：邏輯結構反映數據元素之間的邏輯關系，線性結構表示數據元素之間為一對一的關系，非線性結構表示數據元素之間為一對多或者多對一的關系，所以答案為B）。
答案：B）
【例3】以下_______不是棧的基本運算。（考點5）
A）判斷棧是否為素空 B）將棧置為空棧
C）刪除棧頂元素 D）刪除棧底元素
解析：棧的基本運算有：入棧，出棧（刪除棧頂元素），初始化、置空、判斷棧是否為空或滿、提取棧頂元素等，對棧的操作都是在棧頂進行的。
答案：D）
【例4】鏈表不具備的特點是_______。（考點6）
A）可隨機訪問任意一個結點 B）插入和刪除不需要移動任何元素
C）不必事先估計存儲空間 D）所需空間與其長度成正比
解析：順序表可以隨機訪問任意一個結點，而鏈表必須從第一個數據結點出發，逐一查找每個結點。所以答案為A）。
答案：A）
【例5】已知某二叉樹的後序遍歷序列是DACBE，中序遍歷序列是DEBAC，則它的前序遍歷序列是_______。（考點8）
A）ACBED B）DEABC
C）DECAB D）EDBAC
解析：後序遍歷的順序是"左子樹－右子樹－根結點"；中序遍歷順序是"左子樹－根結點－右子樹"；前序遍歷順序是"根結點－左子樹－右子樹"。根據各種遍歷演算法，不難得出前序遍歷序列是EDBAC。所以答案為D）。
答案：D）
【例6】設有一個已按各元素的值排好序的線性表（長度大於2），對給定的值k，分別用順序查找法和二分查找法查找一個與k相等的元素，比較的次數分別是s和b，在查找不成功的情況下，s和b的關系是_______。（考點9）
A）s=b B）s>b C）s<b D）s≥b
解析：對於順序查找，查找不成功時和給定關鍵字比較的次數為n+1。二分查找查找不成功的關鍵字比較次數為〔log2n〕+1。當n≥2時，顯然n+1>〔log2n〕+1。
答案：B）
【例7】在快速排序過程中，每次劃分，將被劃分的表（或子表）分成左、右兩個子表，考慮這兩個子表，下列結論一定正確的是_______。（考點11）
A）左、右兩個子表都已各自排好序
B）左邊子表中的元素都不大於右邊子表中的元素
C） 左邊子表的長度小於右邊子表的長度
D）左、右兩個子表中元素的平均值相等
解析：快速排序基本思想是：任取待排序表中的某個元素作為基準（一般取第一個元素），通過一趟排序，將待排元素分為左右兩個子表，左子表元素的排序碼均小於或等於基準元素的排序碼，右子表的排序碼則大於基準元素的排序碼，然後分別對兩個子表繼續進行排序，直至整個表有序。
答案：B）
二、填空題
【例1】問題處理方案的正確而完整的描述稱為_______。（考點1）
解析：計算機解題的過程實際上是在實施某種演算法，這種演算法稱為計算機演算法。
答案：演算法
【例2】一個空的數據結構是按線性結構處理的，則屬於_______。（考點4）
解析：一個空的數據結構是線性結構或是非線性結構，要根據具體情況而定。如果對數據結構的運算是按線性結構來處理的，則屬於線性結構，否則屬於非線性結構。
答案：線性結構
【例3】設樹T的度為4，其中度為1、2、3和4的結點的個數分別為4、2、1、1，則T中葉子結點的個數為_______。（考點7）
解析：根據樹的性質：樹的結點數等於所有結點的度與對應的結點個數乘積之和加1。
因此樹的結點數為1×4＋2×2＋3×1＋4×1＋1＝16。葉子結點數目等於樹結點總數減去度不為0的結點數之和，即16－（4＋2＋1＋1）＝8。
答案：8
【例4】二分法查找的存儲結構僅限於_______且是有序的。（考點10）
解析：二分查找，也稱折半查找，它是一種高效率的查找方法。但二分查找有條件限制：要求表必須用順序存儲結構，且表中元素必須按關鍵字有序(升序或降序均可）。
答案：順序存儲結構
④ 排序演算法最快的是哪種說說原理，哪些是不用申請額外空間的
沒有哪一種永遠最快，要看場合，也要看這個最快是哪個指標，並且要考慮數據的規模，還要看是否穩定，有時存儲結構同樣不能排除
至於不用申請額外空間的，只要是原地排序的都是，比如：
直接插入，希爾排序，冒泡排序、直接選擇排序、堆排序等
⑤ 遞歸的空間復雜度
遞歸折半查找的時間復雜度是O(log2n)，空間復雜度是O(log2n)，也是遞歸的最大深度
非遞歸的時間復雜度是O(log2n)，空間復雜度是O(1)，僅僅用幾個單變數就夠。空間復雜度:
是程序運行所以需要的額外消耗存儲空間,一般的遞歸演算法就要有o(n)的空間復雜度了,簡單說就是遞歸集算時通常是反復調用同一個方法，遞歸n次，就需要n個空間。
時間復雜度：
一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。
一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f (n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。
在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n2)。
按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n),線性階O(n
k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。
⑥ 演算法復雜度的空間復雜度
與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作:
S(n)=O(f(n))
演算法執行期間所需要的存儲空間包括3個部分：
·演算法程序所佔的空間；
·輸入的初始數據所佔的存儲空間；
·演算法執行過程中所需要的額外空間。
在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術。
⑦ 演算法時間復雜度x=2 while(x<n/2) x=2*x 求演算法時間復雜度
演算法時間復雜度為：O（log₂n）。
演算法復雜度是指演算法在編寫成可執行程序後，運行時所需要的資源，資源包括時間資源和內存資源。應用於數學和計算機導論。與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作：S（n）＝O（f（n））。
演算法執行期間所需要的存儲空間包括3個部分：演算法程序所佔的空間；輸入的初始數據所佔的存儲空間；演算法執行過程中所需要的額外空間。在許多實際問題中，為了減少演算法所佔的存儲空間，通常採用壓縮存儲技術。