一放吩、數(shù)據(jù)結(jié)構(gòu)的基本概念
1. 數(shù)據(jù):
描述客觀事物的符號, 是計(jì)算機(jī)中可以操作的對象, 是被計(jì)算機(jī)識別, 并輸入給計(jì)算機(jī)處理的符號集合.
數(shù)據(jù)不僅僅包括整型,實(shí)型等基本數(shù)據(jù)結(jié)構(gòu), 還包括網(wǎng)頁, 音頻, 視頻, 圖片等
2. 數(shù)據(jù)元素
組成數(shù)據(jù)的, 有一定意義的基本單位, 在計(jì)算機(jī)中通常作為整體處理, 也被稱為記錄.
比如:
- 把人類當(dāng)做數(shù)據(jù), 那么數(shù)據(jù)元素就是每一個(gè)人.
- 把禽畜當(dāng)做數(shù)據(jù)敷搪， 那么牛哀蘑， 馬派草， 羊，雞等就是數(shù)據(jù)元素他匪。
3.數(shù)據(jù)項(xiàng)
一個(gè)數(shù)據(jù)元素是有若干個(gè)數(shù)據(jù)項(xiàng)組成的片择， 數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位
比如人是數(shù)據(jù)元素， 那么人身上的眼拴疤， 耳永部， 鼻，嘴等就是數(shù)據(jù)項(xiàng)
4.數(shù)據(jù)對象
性質(zhì)相同的數(shù)據(jù)元素的集合呐矾， 時(shí)數(shù)據(jù)的子集苔埋。
可以理解為數(shù)據(jù)
5.數(shù)據(jù)結(jié)構(gòu)
是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合
結(jié)構(gòu)， 簡單的理解就是關(guān)系蜒犯， 比如分子結(jié)構(gòu)组橄，就是說組成分子的原子之間的排列方式。 不同的數(shù)據(jù)元素之間不是獨(dú)立的罚随， 而是存在特定的關(guān)系玉工，我們將這些關(guān)系稱為結(jié)構(gòu)
按視點(diǎn)的不同， 我們把數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)淘菩。
邏輯結(jié)構(gòu)
是指數(shù)據(jù)對象中數(shù)據(jù)袁術(shù)之間的互相關(guān)系
- 集合結(jié)構(gòu)
- 線性結(jié)構(gòu)
- 樹形結(jié)構(gòu)
- 圖形結(jié)構(gòu)
物理結(jié)構(gòu)
是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲形式
- 順序存儲結(jié)構(gòu)： 排隊(duì)形式
- 鏈?zhǔn)酱鎯Y(jié)構(gòu)： 指針的形式
二遵班、算法的基本概念
算法的定義： 算法是解決特定問題求解步驟的描述屠升， 在計(jì)算機(jī)中為指令的有限序列， 并且每條指令表示一個(gè)或者多個(gè)操作
算法的特性： 有窮性狭郑，確定性腹暖， 可行性， 輸入翰萨， 輸出脏答。
算法的設(shè)計(jì)要求： 正確性， 可讀性亩鬼， 健壯性殖告， 高效率， 和低存儲量需求
算法的度量方法：
- 事后統(tǒng)計(jì)方法 （不科學(xué)辛孵， 不準(zhǔn)確丛肮， 因?yàn)椴煌挠?jì)算機(jī)硬件， 內(nèi)存魄缚， 平臺的因素影響）
- 事前分析估算方法
函數(shù)的漸進(jìn)增長： 給定兩個(gè)函數(shù) f(n) 和 g(n), 如果存在一個(gè)整數(shù) N 宝与， 使得對于所有的 n > N, f（n）總是比 g（n）大， 那么冶匹， 我們說f（n）的增長漸進(jìn)快于g（n）习劫。 于是我們可以得出一個(gè)結(jié)論， 判斷一個(gè)算法好不好嚼隘， 我們只通過少量的數(shù)據(jù)是不能作出準(zhǔn)確判斷的诽里， 如果我們可以對比算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)的漸進(jìn)增長性， 基本就可以分析出： 某個(gè)算法飞蛹， 隨著n的變大谤狡， 它會越來越優(yōu)于另一算法， 或者越來越差于另一算法卧檐。
然后給出了算法事件的復(fù)雜度的定義和推導(dǎo)大 O 階的步驟墓懂。
推導(dǎo)大 O 階：
- 用常數(shù) 1 取代運(yùn)行時(shí)間中的所有加法常熟
- 在修改的運(yùn)行次數(shù)函數(shù)中， 只保留最高階的常數(shù)
- 如果最高階項(xiàng)存在且不是 1 霉囚， 則去除與這個(gè)項(xiàng)相乘的常數(shù)
得到的結(jié)果就是 大O階捕仔。
常見的事件復(fù)雜度所耗時(shí)間的大小排列：
O(1) < O(logn) < O(n) < O(nlogn) < O(n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
