了解數據結構和算法的壹些基本概念,主要掌握時間復雜度的計算
數據結構是指所有數據元素以及數據元素之間的關系,可以看做是相互之間存在著某種特定關系的數據元素的集合,即可以把數據結構看成是 帶結構的數據元素的集合 。
數據的邏輯結構是從邏輯關系上描述數據的,常常將數據的邏輯結構簡稱為數據結構。
集合:
樹形結構:
圖形結構:
邏輯結構在計算機中的存儲方式。依賴於計算機語言
順序存儲結構:
鏈式存儲結構:
索引存儲結構:
散列(哈希)存儲結構:
數據類型是壹組性質相同的值的集合和定義在此集合上的壹組操作的總稱,數據類型是數據結構在計算機的具體體現。
註意:
算法是對特定問題求解步驟的壹種描述
特性: 有窮性、確定性、可行性、有輸入、有輸出
算法設計好後,還需要分析算法的優劣,從兩方面考慮
壹個算法由控制結構和原操作構成,算法的運算時間取決於兩者的綜合效果,算法執行時間大致為基本運算時所需時間與運行次數的乘積。因此壹個算法的執行效率可以由其最基本的運算的執行次數來衡量。
計算公式: T(n)=O(f(n))
說明:
註意: O 的作用在於只求出T(n)的最高階項,忽略低階項和常數
O(1)
沒有進行循環的算法中,基本運算次數與問題規模無關,所以是常數
對數階 O(log2n)
次數為x,而2的x次方等於n,那麽就是對數階
線性階 O(n)
只有壹層循環
平方階 O(n^2)
立方階 O(n^3)
三層循環,肯定就是n^3了
排序:
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) <O(2^n) < O(n!) < O(n^n)
也叫加權平均時間復雜度,將執行的概率也加入計算。
是壹種特殊的加權平均時間復雜度,把耗時多的操作分攤到耗時低的操作。
這個時間復雜度 其實是O(1),而不是O(n)
算法空間復雜度是指計算算法所需的存儲空間, 其計算公式為S(n) = n(f(n))
所以在考察算法的空間復雜度,主要考慮算法執行所需要的臨時占用的存儲空間大小的量度。
數組逆序,將壹維v1.43數組a中的n個數逆序存放在原數組中.
復雜度計算:
說明: