演算法認知

① 關於演算法

阿朱對於演算法的了解不多，總結如下，希望多多交流，改正瑕疵。

演算法推薦主要有5種方式：

基於內容推薦：這是基於用戶個人興趣的推薦。根據用戶個體的歷史行為，計算對內容特徵的偏好程度，進而推薦出與用戶特徵偏好匹配的內容。

協同過濾演算法：這是基於群體的推薦。基於用戶的相似度、內容的共現度，以及基於人口特徵將用戶聚集為不同群體來推薦。（解釋一下：常見的協同過濾演算法有兩種，一種是基於用戶的（user-based），也即計算用戶之間的相似性，如果A和B的興趣相近，那麼A喜歡的電影，B也很有可能喜歡。另一種是基於物品的（item-based），也即計算物品之間的相似性，如果電影C和電影D很相似，那麼喜歡電影C的人，可能也會喜歡電影D。）

擴展推薦：基於用戶興趣點、內容類別等擴展。（你喜歡歷史資訊，我推考古、尋寶的資訊給你）

新熱推薦：基於全局內容的時效性、熱度推薦。（在產品初期同時缺乏用戶數據和內容數據時，內容分發效率很低。使用基於內容推薦演算法效果不顯著，而使用一些熱點話題可在保證一定流量的同時，不斷通過用戶的個人行為（點贊、評論、瀏覽、收藏）來逐步精確用戶畫像和進行內容沉澱，為之後的個性化推薦做准備）。

環境特徵：基於地域、時間、場景等推薦。（知乎上你們市的牙科診所廣告、婚慶廣告）

每種演算法的效果不一，組合味道更佳，因此很多公司都是採用「演算法矩陣」的方式來推薦feed。（後文也會談到這一點）

優勢:

內容質量審核、社區治理（辱罵、撕逼），推薦商品，減少人工運營成本。

源源不斷推薦給你感興趣的feed，提升了用戶粘性，商業化的潛力進一步加大。

讓用戶 kill time 的需求更好地被滿足，增強用戶體驗

弊端：

1.演算法本身或者演算法背後的人產生技術錯誤——只要是人寫的演算法，就一定有出錯的概率，比如德國居民凌晨發飆的智能音箱、失控的Uber自動駕駛汽車就是程序上的Bug導致的，這一類我們克服的辦法其實相對簡單。但對於另一種人為算計消費者的演算法有時候可能我們就無能為力了，比如大數據殺熟現象，無論真實與否，這類問題往往很難識別，因此也加大了監管的難度；（抖音視頻里你見不到「錢」字，只能看到「Q」來代替）

2.演算法對於人性部分的忽略——現在的人工智慧離真正理解人類的感情和行為依然有巨大的鴻溝，Facebook提醒你給去世的親人發生日祝福背後本質的原因在於AI無法真正理解死亡對於人類意味著什麼；因此需要人機結合（平台人工參與，用戶舉報等自治措施），不能單獨依靠演算法。

3.演算法訓練數據本身的偏見——目前人工智慧的基本邏輯是先構建一個合適的機器學習模型，然後用大量的數據去訓練模型，然後用訓練好的模型再來預測新的數據，這里邊有一個非常重要前提就是輸入數據的重要性，比如變壞的微軟機器人Tay之所以產生問題就是因為輸入的數據中本身就存在偏見，如果現實世界數據本身就存在偏見，那麼預測結果也一定會有偏見；

先下結論吧：演算法不會導致「信息繭房」

「社交媒體和演算法推薦導致信息繭房」這一判斷成立的一個重要前提是：我們只會點擊那些我們熟悉的、贊同的內容，不斷讓機器加深對我們的印象：原來他們只喜歡看這些！

但在現實中，這個前提是過於簡化的，乃至是錯誤的。

在個體層面，我們有著多樣的閱讀動機，受到各種認知偏見的影響，可能傾向於點擊某些特定類型的內容，但絕不僅僅局限於自己認同的那些。

在社交層面：我們在大多數APP上都存在著社交關系，以及主動選擇關注的帳號，這些都對我們能接觸到的內容產生重要影響。一個在APP上擁有一定社交關系的人，不太可能陷入狹窄的視野當中。

在技術層面：在演算法的分類里說了，每種演算法都有其利弊，因此很多公司都是採用「演算法矩陣」的方式來推薦feed。但在普羅大眾眼裡，演算法=基於內容的推薦演算法，而忽略了「基於內容的推薦演算法」只是演算法種類里的一種，其他類型演算法也會被產品使用。

在企業層面：沒有一個商場的經理，希望顧客每一次來到商場都只關注同一類別的商品。用戶興趣窄化對於商業化目標並不是一個好的選擇。

博弈：

推薦太強了，關注力量就會弱。抖音沉浸式交互和基於內容的演算法推薦是 kill time 的利器，推薦feed刷的過癮了，你還會去刷關注feed嗎？

共生：

演算法有弊端，關注可以彌補或有所增益。推薦feed是忽略了人"社交性「這個特點，以知乎為例，關注的內容生產者傳遞給我們價值，所以我們需要一個途徑來知道那幾十個或上百的關注對象的產出內容。朋友圈滿足我們窺探的信息需求，也同理。（另外從結果反推過程，大家看一下手裡的B站、知乎、抖音、快手就清楚了）

② 什麼是演算法

演算法（Algorithm）是指解題方案的准確而完整的描述，是一系列解決問題的清晰指令，演算法代表著用系統的方法描述解決問題的策略機制。也就是說，能夠對一定規范的輸入，在有限時間內獲得所要求的輸出。如果一個演算法有缺陷，或不適合於某個問題，執行這個演算法將不會解決這個問題。不同的演算法可能用不同的時間、空間或效率來完成同樣的任務。一個演算法的優劣可以用空間復雜度與時間復雜度來衡量。
演算法中的指令描述的是一個計算，當其運行時能從一個初始狀態和（可能為空的）初始輸入開始，經過一系列有限而清晰定義的狀態，最終產生輸出並停止於一個終態。一個狀態到另一個狀態的轉移不一定是確定的。隨機化演算法在內的一些演算法，包含了一些隨機輸入。
形式化演算法的概念部分源自嘗試解決希爾伯特提出的判定問題，並在其後嘗試定義有效計算性或者有效方法中成形。這些嘗試包括庫爾特·哥德爾、Jacques Herbrand和斯蒂芬·科爾·克萊尼分別於1930年、1934年和1935年提出的遞歸函數，阿隆佐·邱奇於1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾倫·圖靈1937年提出的圖靈機。即使在當前，依然常有直覺想法難以定義為形式化演算法的情況。

③ 一文帶你認識30個重要的數據結構和演算法

數組是最簡單也是最常見的數據結構。它們的特點是可以通過索引（位置）輕松訪問元素。

它們是做什麼用的？

想像一下有一排劇院椅。每把椅子都分配了一個位置（從左到右），因此每個觀眾都會從他將要坐的椅子上分配一個號碼。這是一個數組。將問題擴展到整個劇院（椅子的行和列），您將擁有一個二維數組（矩陣）。

特性

鏈表是線性數據結構，就像數組一樣。鏈表和數組的主要區別在於鏈表的元素不存儲在連續的內存位置。它由節點組成——實體存儲當前元素的值和下一個元素的地址引用。這樣，元素通過指針鏈接。

它們是做什麼用的？

鏈表的一個相關應用是瀏覽器的上一頁和下一頁的實現。雙鏈表是存儲用戶搜索鍵嘩顯示的頁面的完美數據結構。

特性

堆棧是一種抽象數據類型，它形式化了受限訪問集合的概念。該限制遵循 LIFO（後進先出）規則。因此，添加到堆棧中的最後一個元素是您從中刪除的第一個元素。

堆棧可以使用數組或鏈表來實現。

它們是做什麼用的？

現實生活中最常見的例子是在食堂中將盤子疊放在寬枝一起。位於頂部的板首先被移除。放置在最底部的盤子是在堆棧中保留時間最長的盤子。

堆棧最有用的一種情況是您需要獲取給定元素的相反順序。只需將它們全部推入堆棧，然後彈出它們。

另一個有趣的應用是有效括弧問題。給定一串括弧，您可以使用堆棧檢查它們是否匹配。

特性

隊列是受限訪問集合中的另一種數據類型，就像前面討論的堆棧一樣。主要區別在於隊列是按照FIFO（先進先出）模型組織的：隊列中第一個插入的元素是第一個被移除的元素。隊列可以使用固定長度的數組、循環數組或鏈表來實現。

它們是做什麼用的？

這種抽象數據類型 (ADT) 的最佳用途當然是模擬現實生活中的隊列。例如，在呼叫中心應用程序中，隊列用於保存等待從顧問那裡獲得幫助的客戶——這些客戶應該按照他們呼叫的順序獲得幫助。

一種特殊且非常重要的隊列類型是優先順序隊列。元素根據與它們關聯的「優先順序」被引入隊列：具有最高優先順序的元素首先被引入隊列。這個 ADT 在許多圖演算法（Dijkstra 演算法、BFS、Prim 演算法、霍夫曼編碼 ）中是必不可少的。它是使用堆實現的。

另一種特殊類型的隊列是deque 隊列（雙關語它的發音是「deck」）。可以從隊列的兩端插入/刪除元素。

特性

Maps （dictionaries）是包含鍵集合和值集合的抽象數據類型。每個鍵都有一個與之關聯的值。

哈希表是一種特殊類型的映射。它使用散列函數生成一個散列碼，放入一個桶或槽數組：鍵被散列，結果散列指示值的存儲位置。

最常見的散列函數（在眾多散列函數中）是模常數函數。例如，如果常量是 6，則鍵 x 的值是x%6。

理想情況下，散列函數會將每個鍵分配給一個唯一的桶，但他們的大多數設計都採用了不完善的函數，這可能會導致具有相同生成值的鍵之間發生沖突。這種碰撞總是以某種方式適應的。

它們是做什麼用的？

Maps 最著名的應用是語言詞典。語言中的每個詞都為其指定了定義。它是使用有序映射實現的（其鍵按字母順序排列）。

通訊錄也是一張Map。每個名字都有一個分配給它的電話號碼。

另一個有用的應用是值的標准化。假設我們要為一天中的每一分鍾（24 小時 = 1440 分鍾）分配一個從 0 到 1439 的索引。哈希函數將為h(x) = x.小時*60+x.分鍾。

特性

術語：

因為maps 是使用自平衡紅黑樹實現的（文章後面會解釋），所以所有操作都在 O(log n) 內完成；所有哈希表操作都是常量。

圖是表示一對兩個集合的非線性數據結構：G={V, E}，其中 V 是頂點（節點）的集合，而 E 是邊（箭頭）的集合。節點是由邊互連的值 - 描述兩個節點之間的依賴關系（有時與成本/距離相關聯）的線。

圖有兩種主要類型：有稿巧行向圖和無向圖。在無向圖中，邊(x, y)在兩個方向上都可用：(x, y)和(y, x)。在有向圖中，邊(x, y)稱為箭頭，方向由其名稱中頂點的順序給出：箭頭(x, y)與箭頭(y, x) 不同。

它們是做什麼用的？

特性

圖論是一個廣闊的領域，但我們將重點介紹一些最知名的概念：

一棵樹是一個無向圖，在連通性方面最小（如果我們消除一條邊，圖將不再連接）和在無環方面最大（如果我們添加一條邊，圖將不再是無環的）。所以任何無環連通無向圖都是一棵樹，但為了簡單起見，我們將有根樹稱為樹。

根是一個固定節點，它確定樹中邊的方向，所以這就是一切「開始」的地方。葉子是樹的終端節點——這就是一切「結束」的地方。

一個頂點的孩子是它下面的事件頂點。一個頂點可以有多個子節點。一個頂點的父節點是它上面的事件頂點——它是唯一的。

它們是做什麼用的？

我們在任何需要描繪層次結構的時候都使用樹。我們自己的家譜樹就是一個完美的例子。你最古老的祖先是樹的根。最年輕的一代代表葉子的集合。

樹也可以代表你工作的公司中的上下級關系。這樣您就可以找出誰是您的上級以及您應該管理誰。

特性

二叉樹是一種特殊類型的樹：每個頂點最多可以有兩個子節點。在嚴格二叉樹中，除了葉子之外，每個節點都有兩個孩子。具有 n 層的完整二叉樹具有所有2ⁿ-1 個可能的節點。

二叉搜索樹是一棵二叉樹，其中節點的值屬於一個完全有序的集合——任何任意選擇的節點的值都大於左子樹中的所有值，而小於右子樹中的所有值。

它們是做什麼用的？

BT 的一項重要應用是邏輯表達式的表示和評估。每個表達式都可以分解為變數/常量和運算符。這種表達式書寫方法稱為逆波蘭表示法 (RPN)。這樣，它們就可以形成一個二叉樹，其中內部節點是運算符，葉子是變數/常量——它被稱為抽象語法樹（AST）。

BST 經常使用，因為它們可以快速搜索鍵屬性。AVL 樹、紅黑樹、有序集和映射是使用 BST 實現的。

特性

BST 有三種類型的 DFS 遍歷：

所有這些類型的樹都是自平衡二叉搜索樹。不同之處在於它們以對數時間平衡高度的方式。

AVL 樹在每次插入/刪除後都是自平衡的，因為節點的左子樹和右子樹的高度之間的模塊差異最大為 1。 AVL 以其發明者的名字命名：Adelson-Velsky 和 Landis。

在紅黑樹中，每個節點存儲一個額外的代表顏色的位，用於確保每次插入/刪除操作後的平衡。

在 Splay 樹中，最近訪問的節點可以快速再次訪問，因此任何操作的攤銷時間復雜度仍然是 O(log n)。

它們是做什麼用的？

AVL 似乎是資料庫理論中最好的數據結構。

RBT（紅黑樹） 用於組織可比較的數據片段，例如文本片段或數字。在 Java 8 版本中，HashMap 是使用 RBT 實現的。計算幾何和函數式編程中的數據結構也是用 RBT 構建的。

在 Windows NT 中（在虛擬內存、網路和文件系統代碼中），Splay 樹用於緩存、內存分配器、垃圾收集器、數據壓縮、繩索（替換用於長文本字元串的字元串）。

特性

最小堆是一棵二叉樹，其中每個節點的值都大於或等於其父節點的值：val[par[x]]

④ 01 - 數據結構和演算法的認識

了解數據結構和演算法的一些基本概念，主要掌握時間復雜度的計算

數據結構是指所有數據元素以及數據元素之間的關系，可以看做是相互之間存在著某種特定關系的數據元素的集合，即可以把數據結構看成是 帶結構的數據元素的集合 。

數據的邏輯結構是從邏輯關繫上描述數據的，常常將數據的邏輯結構簡稱為數據結構。

集合：

樹形結構：

圖形結構：

邏輯結構在計算機中的存儲方式。依賴於計算機語言

順序存儲結構：

鏈式存儲結構：

索引存儲結構：

散列（哈希）存儲結構：

數據類型是一組性質相同的值的集合和定義在此集合上的一組操作的總稱，數據類型是數據結構在計算機的具體體現。

注意：

演算法是對特定問題求解步驟的一種描述

特性： 有窮性、確定性、可行性、有輸入、有輸出

演算法設計好後，還需要分析演算法的優劣，從兩方面考慮

一個演算法由控制結構和原操作構成，演算法的運算時間取決於兩者的綜合效果，演算法執行時間大致為基本運算時所需時間與運行次數的乘積。因此一個演算法的執行效率可以由其最基本的運算的執行次數來衡量。

計算公式： 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個數逆序存放在原數組中.

復雜度計算:

說明：