資料結構-搜尋與排序
考研相關文章參考資料為 wjungle 大神提供的筆記
Search
Linear Search
又稱為 Sequential Search,從頭到尾一一比較是否符合
特性:
不必事先進行排序
資料可以保存在 Ramdom Access (array) 或 Sequentail Access (link list) 結構中
時間複雜度: O(n)O(n)O(n)
Binary Search
預先準備
必須將資料排序 (小 -> 大)
資料必須保存在 Ramdom Access (array) 結構
可以做成 Iterative / Recursive 版本
時間複雜度: O(logn)O(\log n)O(logn)
最多比較次數為 Decision Tree (高度最小化的 BT) 之樹高
名詞區分
Worst case:
Binary Search: O(logn)O(\log n)O(logn)
Binary Search Tree: O(n)O(n)O(n) (斜曲)
Sort
名詞解釋
Internal / External ...
資料結構-高等樹
考研相關文章參考資料為 wjungle 大神提供的筆記
Doubled-ended priority Queue
兩端皆可插入元素,一端提供 deleteMax,一端提供 deleteMin
資料結構:
Min-Max Heap
Deap
SMMH
提供操作:
Insert x
Delete-Max
Delete-Min
Min-Max Heap
是一個 Complete BT,並且滿足:
level 以 min-level 與 max-level 交替出現
xxx 位於 min-level: 以 xxx 為 root 之子樹中,xxx 為最小值
xxx 位於 max-level: 以 xxx 為 root 之子樹中,xxx 為最大值
Root 位於 min-level
Insert x
把 xxx 放到最後一個節點的下一個位置
根據 xxx 的父節點 p 所在 level 進行挑戰
如果挑戰父節點成功: 將父節點下移,並挑戰父節點原本位置的祖父節點
挑戰失敗: 挑戰祖父節點
Delete-Min
刪除 root 的資料,並且刪除最後一個節 ...
資料結構-樹與二元樹
考研相關文章參考資料為 wjungle 大神提供的筆記
樹 (Tree)
由 >0 個節點 (Node) 所構成
森林 (Forest): 由 >=0 個樹所構成 (可以為空)
表示方式
Link list
Node: | Data | child 1 | child 2 | … | child k
假設 degree 為 kkk,並且有 nnn 個節點,會浪費 n∗k−(n−1)n*k-(n-1)n∗k−(n−1) 條 Link (Nil links)
轉為二元樹表示
Child-sibling 方法
Node: | Data | child | sibling |
child: 指向 leftmost-child
sibling: 指向 次右兄弟
括號法
以 父(子1,子2,...子n) 表示父點與子點之間的關係,並且可以巢狀方式表示
二元樹 (BT)
可以為空,若不為空則滿足:
有 root 及左右子樹
左右子樹也是二元樹
與樹比較:
樹
二元樹
不能為空
可以為空
degree≥0degree \ge ...
發展心理學筆記-L12
L12 Work: Occupational and Lifestyle Issues in Young and Middle Adulthood
Occupational Selectionn and Development
The Meaning of Work
多數人認為工作的意義:
賺錢
個人成長
個人成就
發展自我
與人合作
表達自我
為他人服務
Meaning-mission fit
個人意向公司的目標是否相符
如果相符的話,會提高幸福感以及工作滿意度
Occupational Choice Revisited
工作選擇相關理論:
Career construction theory 生涯建構論
人們通過個人特質和社會環境產生的行動來選擇職業
Holland’s personality-type theory 人格類型論
人們根據個人特質與職業之間的契合度選擇工作
Social cognitive career theory (SCCT) 社會認知生涯論
職業選擇是 Bandura 社會認知理論的應用,特別是 self-efficac ...
通訊原理筆記-L10
L10 Existing Wireless Systems
History of Mobile Telecommunication Systems
1G
1980 年代初
Analog communication technique (類比)
Cell 範圍大,頻譜利用率低
行動裝置尺寸大
2G
1990 年代初
Digital communication technology (數位)
更好的頻譜利用率,裝置價格較低
初始支援音訊,後來加入 short message service (SMS)
系統:
GSM (Global System for Mobile Communications) - 歐洲
IS-95 (cdma-One) - 高通所設計
2.5G
網路開始發展,有傳送資料的需求
GPRS (General Packet Radio Service) 搭配 GSM
IS-95B 搭配 IS-95
3G
2000 年後
網路需要更大的 data rates
系統:
UMTS (Universal Mobile Telecommunicatio ...
發展心理學筆記-L11
L11 Being With Others: Forming Relationships in Young and Middle Adulthood
Relationships
Friendships
特徵
based on feelings and reciprocity (互惠)
相較於愛情有較少的情感以及性要素
良好的友誼可以提高自尊
ABCDE model (友誼的各個階段)
acquaintanceship (熟人)
buildup
continuation
deterioration (惡化)
ending
人生階段
在 young adulthood 相較其他時期擁有更多的 friends and acquaintance
Life transitions (ex: 結婚) 朋友會減少
Online Age
大量網路用戶 - 朋友增加
online friendships:
需要 信任
也有可能像是現實的朋友那樣強的關係
有利於害羞的人
男女差異
女 - 情緒分享 & 信任
男 - 共同活動、興趣
異性友誼
Men with ...
通訊原理筆記-L9
L9 Mobile Communication Systems
Cellular System Infrastructure
BS = base transceiver system (BTS) + BS controller (BSC)
BTS: tower + antenna
BSC: electronics (電路)
AUC (Authentication center)
驗證與加密,確認使用者身分
EIR (Equipment identity register)
資料庫儲存行動設備的識別碼與資訊
HLR (Home location register)
紀錄在 MS 初始註冊時的 MSC (mobile switching center)
包含課費資訊等基礎資料
VLR (Visitor location register)
記錄目前在該 MSC 區域活動的 MS 資訊
指向其對應 HLR 的指標
MS 跟 serving BS 註冊,BS 將 MS 登錄在 visiting MSC 的 VLR,MSC 再登錄在 home MSC的 HLR ...
通訊原理筆記-L8
L8 Traffic Channel Allocation
Channel Allocation
將頻譜 (radio spectrum) 分割成多個互不重疊的通道 (channels),讓使用者可以同時使用,並且盡可能地減少干擾
Static vs. Dynamic
Static - 每個 cell 被分配了一組固定的頻道數量
equal: 每個 cell 分配相同數量
non-uniform: 每個 cell 根據需求分配數量
Dynamic - 根據需求,動態分配頻道給需要的 cell
分類:
Fixed Channel Allocation schemes (FCA schemes)
Dynamic Channel Allocation schemes (DCA schemes)
Hybrid Channel Allocation schemes (HCA schemes)
FCA
A set of channels is permanently allocated to each cell
因為 traffic 的短期波動 (使用者數量改變) ...
通訊原理筆記-L7
L7 Multiple Division Techniques
Motivation: to have many traffic channels
分類:
Frequency: FDMA (Frequency Division Multiple Access)
Time: TDMA (Time Division Multiple Access)
Code: CDMA (Code Division Multiple Access)
SDMA (Space Division Multiple Access)
Models of Multiple Divisions
Forward (Downlink) Channel: 基地台 (BS) -> 行動裝置 (MS)
Reverse (Uplink) Channel: MS -> BS
Duplex Communications (雙向通訊)
Full Duplex (全雙工) - 上下行可以同時進行
Half Duplex (半雙工) - 上下行不能同時進行,只能交替發送與接收
Type:
FDD (frequenc ...
通訊原理筆記-L6
L6 Multiple Radio Access
Multiple Radio Access Protocols
行動與無線通訊中用來讓多個使用者在共享的頻譜或頻道上有效通訊的技術集合
Multiple Access Protocols 分類:
Contention-based - 競爭通道使用權,可能發生碰撞
Aloha
CSMA
對應 Control channel - L6
Conflict free - 預先分配資源,避免碰撞
FDMA
TDMA
CDMA
對應 Data channel (traffic channel) - L7
Pure ALOHA
最早的 random-access method
Rules:
Multiple access: a station sends a frame when it has a frame to send
Acknowledgment: the station waits for an ACK after its transmission
Allotted time: 2 times the max pr ...














