5分鍾學演算法網站

㈠ PageRank演算法實現好友推薦(演算法原理)

對於社交系統與電商網站，推薦系統佔有很重要的位置，當數據量越來越大的時候，用戶無法確定該選擇什麼商品，因此在電商系統中需要按照興趣或者相似度給用戶推薦相應的商品。相應的，在一個大型社交網路平台中，對於一些用戶，我們希望推薦一些知名度較高，活躍度較高或者感興趣的用戶，比如一些明星，歌手，演員等等。在社交網路中，PageRank演算法有著廣泛的應用，因此，本篇文章主要介紹其原理。

對於大部分社交系統來說，如果只是簡單的獲取好友的信息遠遠不夠，我們可以通過獲取好友的好友的信息來擴展用戶的朋友圈，使得信息量更加豐富，本項目中使用PageRank演算法來完成二級鄰居，然後按照Rank排序，選擇Top5用戶實現用戶的好友的好友的推薦。

PageRank演算法由Google的創始人拉里·佩奇和謝爾·布林於1998年發明.這項技術設計之初是為了體現網頁的相關性和重要性,在搜索引擎優化操作中經常被用來評估網頁優化的成效因素之一.

從技術上看,搜索引擎需要解決以下三個問題:

本質就是一個爬蟲問題,通過爬蟲獲取整個互聯網的數據

關鍵在於快速找到.

它的實現方式有: 倒排索引，簽名文件，後綴樹等。我們最熟悉的是 倒排索引 。(並不熟悉,以後有機會再看)

排序是Google的搜索引擎能夠興起的一個決定性因素。

對網頁排序有很多種方式，我們來看三種：

就是原封不懂地把索引到的鏈接直接返回給用戶，缺點就不說了，想找自己感興趣的內容估計要費不少功夫。

這種方式是一種只從關鍵詞出現的次數和位置進行排序的方法。該方法以一個關鍵詞與網頁的相關度大小作為排序標准，而關鍵詞在網頁的相關度大小作為排序標准，而關鍵詞在網頁中的相關度則由它在網頁中出現的頻次和位置兩方面加權計算得出。

缺點也很明顯，容易出現刷分的情況，整篇文章中大量地刷關鍵詞就能提高排名。

真正找到計算網頁自身質量的完美的數學模型是Google的創始人拉里佩奇和謝爾蓋布林。 下一節講一下原理。

我們模擬一個悠閑的上網者，上網者首先隨機選擇一個網頁打開，然後在這個網頁上呆了幾分鍾後，跳轉到該網頁所指向的鏈接，這樣無所事事、漫無目的地在網頁上跳來跳去，PageRank就是估計這個悠閑的上網者分布在各個網頁上的概率，這個概率就代表這個網頁的重要性.

PageRank主要基於兩個重要的假設：

如果一篇文章被越來越多的人引用，那麼這篇文章可能就是一篇經典之作，如果這篇文章引用了其他的論文，那麼一定程度上這篇被引用的文章也是一篇很好的文章。應用到社交網路中，如果一個好友被更多的人關注，那麼說明該好友有很高的知名度和活躍度，那麼，我們可以將該好友推薦給用戶。

基於這兩個假設,我們可以總結出PageRank演算法的核心:

如下圖,可以更好的表達PageRank演算法的思想:

由上圖可知,每個頁面將自己的一部分rank傳遞給某個頁面，我們可以通過計算傳遞給某個頁面的所有rank值的和來計算出它的rank值，當然，不可能是通過一次計算完成，我們剛開始可以給每個頁面賦予一個初始rank值，比如 1/N(N為頁面總數) ，通過迭代計算得到該頁面的rank值。

迭代計算停止的條件為:

使用有向圖表示:

這個例子中只有四個網頁，如果當前在A網頁，那麼悠閑的上網者將會各以1/3的概率跳轉到B、C、D，這里的3表示A有3條出鏈，如果一個網頁有k條出鏈，那麼跳轉任意一個出鏈上的概率是1/k，同理D到B、C的概率各為1/2，而B到C的概率為0。

我們在做計算的時候會將該圖表示成一個二維的矩陣，我們做一個轉換，就會變成下圖的矩陣形式。 M(i,j) 表示j節點指向i節點的概率 ，一般來說每列和為1。

生成的 轉移矩陣 非常簡單, 矩陣的每一列代表該頂點所代表的頁面除以對應頁面的出鏈數得到的 。

有了轉移矩陣，我們可以來定義行向量 V ， V 的第i個分量記錄 對應的Rank值，因此一次Rank的更新可以表示為：

在演算法的第一輪計算中，我們假設上網者在每一個網頁的概率都是相等的，即1/n，於是初試的概率分布就是一個所有值都為1/n的n維列向量 ，用 去右乘轉移矩陣M，就得到了第一步之後上網者的概率分布向量 ,得到一個nX1的矩陣 ， 這個 一輪迭代計算出來的PageRank值 。下面是 的計算過程：

得到了 後，再用 去右乘M得到 ，一直下去，即 , 最終V會收斂 .

不斷的迭代，最終得到結果.

但是在迭代計算中，我們需要考慮如下兩大阻力： Dead End 和 Spider Trap ：

Dead End就是指一個頁面只有入鏈但是沒有出鏈，這時轉移矩陣M的一列為零，導致最後結果為零。這時web不是強連通的，即存在某一類節點不指向別人，如下圖的D。這個時候我們的演算法就會出問題了，它不滿足收斂性了。

為什麼不滿足收斂性了？

Spider Trap指頁面的所有出鏈都指向自己，這樣會使迭代結果中只有自己的頁面的Rank值很高。其他頁面的Rank值為零。

要克服上面兩個問題，我們需要將迭代計算公式做如下轉變。我們可以加入一個 隨機跳轉 機制.

即假設每個頁面有很小概率擁有一個指向其他頁面的鏈接。

表現出來就是：其他頁面本來傳遞給一個頁面的Rank值需要做一個折扣，作為補償，可能需要一個頁面指向該頁面並且傳遞Rank值給該頁面，該跳轉的概率為β，因此表達式變為：

其中,N為頁面總數; e 為一個N維且各個分量都是1的向量;β通過經驗得知一般設為0.15.

此時的計算結果過程為:

有機會再寫,先空著

㈡ 三分鍾了解演算法

數據結構與演算法並不只是抽象的概念，學習過後真的可以在日常工作和生活中用起來，花費最少的時衡消間完成更多的工作才是王道。對於演算法而言學習門檻就有點高了，無論是看書還是網上各種的教學視頻在我們本來就不清楚的情況下引入一堆讓人望而止步的名詞。

這里個人在網路上找到了一些演算法入門的動圖，幫助我們能更快的進入狀態，產生興趣並且提升自己能學好的信念。下面開始動圖的表演，基礎演算法之排序演算法秀。

https://mp.weixin.qq.com/s/8bTPkPlrW1xCo0GoSvy7Jg

1、冒泡排序

提起演算法，無論已經了解了多少演算法知識，第一個想起來的一定是它。

（1）演算法步驟

（2）動圖演示

2、選擇排序

選擇排序是一種簡單直觀的排序演算法，數據規模越小越好。

（ 1）演算法步驟

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。

重復第二步，直到所有元素均排序完畢。

（2）動圖演示

3、插入排序

最容易理解的演算法，想像一下抓了一副撲克，按順序怎麼擺，插入排序的思路就出現了。插入排序是一種最簡單直觀的排序演算法，它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。

（1）演算法步驟

將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最後一個元素當成是未排序序列。

從頭到尾依次掃描未排序序列，將掃描到的每個元素插入有序序列的適當位耐漏置。（如果待插入的元素與有序序列中的某個元素相等，則將待插入元素插入到相等元素的後面。）

（2）動圖演示

4、歸並排序

和選擇排序一樣，歸並排序的性能不受輸入數據的影響，但表現比選擇排序好的多，代價是需要額外的內存空間。

（1）演算法步驟

申請空間，使其大小為兩個已經排序序列之和，該空間昌攔爛用來存放合並後的序列；

設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；

比較兩個指針所指向的元素，選擇相對小的元素放入到合並空間，並移動指針到下一位置；

重復步驟 3 直到某一指針達到序列尾；

將另一序列剩下的所有元素直接復制到合並序列尾。

（2）動圖演示

5、快速排序

處理大數據最快的排序演算法之一了。原因不詳（是個傳說，沒有深究）

（1）演算法步驟

從數列中挑出一個元素，稱為 「基準」（pivot）;

重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作；

遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序；

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

（2）動圖演示

6、計數排序

計數排序的核心在於將輸入的數據值轉化為鍵存儲在額外開辟的數組空間中。作為一種線性時間復雜度的排序，計數排序要求輸入的數據必須是有確定范圍的整數。

（1）動圖演示

7、基數排序

基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。

動圖演示

【原文地址】https://mp.weixin.qq.com/s/8bTPkPlrW1xCo0GoSvy7Jg

㈢ php快速排序演算法實現的原理及代碼詳解

演算法原理
下列動圖來自五分鍾學演算法，演示了快速排序演算法的原理和步驟。
步驟:
從數組中選個基準值
將數組中大於基準值的放同一邊、小於基準值的放另一邊，基準值位於中間位置
遞歸的對分列兩邊的數組再排序
代碼實現
function
quickSort($arr)
{
$len
=
count($arr);
if
($len
<=
1)
{
return
$arr;
}
$v
=
$arr[0];
$low
=
$up
=
array();
for
($i
=
1;
$i
<
$len;
++$i)
{
if
($arr[$i]
>
$v)
{
$up[]
=
$arr[$i];
}
else
{
$low[]
=
$arr[$i];
}
}
$low
=
quickSort($low);
$up
=
quickSort($up);
return
array_merge($low,
array($v),
$up);
}
測試代碼:
$startTime
=
microtime(1);
$arr
=
range(1,
10);
shuffle($arr);
echo
"before
sort:
",
implode(',
',
$arr),
"\n";
$sortArr
=
quickSort($arr);
echo
"after
sort:
",
implode(',
',
$sortArr),
"\n";
echo
"use
time:
",
microtime(1)
-
$startTime,
"s\n";
測試結果:
before
sort:
1,
7,
10,
9,
6,
3,
2,
5,
4,
8
after
sort:
1,
2,
3,
4,
5,
6,
7,
8,
9,
10
use
time:
0.0009009838104248s
時間復雜度
快速排序的時間復雜度在最壞情況下是O(N2)，平均的時間復雜度是O(N*lgN)。
這句話很好理解：假設被排序的數列中有N個數。遍歷一次的時間復雜度是O(N)，需要遍歷多少次呢？至少lg(N+1)次，最多N次。
1)
為什麼最少是lg(N+1)次？快速排序是採用的分治法進行遍歷的，我們將它看作一棵二叉樹，它需要遍歷的次數就是二叉樹的深度，而根據完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數最少是lg(N+1)次。
2)
為什麼最多是N次？這個應該非常簡單，還是將快速排序看作一棵二叉樹，它的深度最大是N。因此，快讀排序的遍歷次數最多是N次。
您可能感興趣的文章:PHP快速排序演算法實例分析PHP四種排序演算法實現及效率分析【冒泡排序,插入排序,選擇排序和快速排序】PHP排序演算法之快速排序(Quick
Sort)及其優化演算法詳解PHP遞歸實現快速排序的方法示例php
二維數組快速排序演算法的實現代碼PHP常用排序演算法實例小結【基本排序，冒泡排序，快速排序，插入排序】PHP快速排序quicksort實例詳解

㈣ 怎麼學好數據結構與演算法，好難啊

李明傑老師：每周一道演算法題 通關演算法面試課（超清視頻）網路網盤

鏈接: https://pan..com/s/14GZpVf03Mf9E-YnMrrR4Pw

若資源有問題歡迎追問~

㈤ 機器學習有哪些演算法

1. 線性回歸
在統計學和機器學習領域，線性回歸可能是最廣為人知也最易理解的演算法之一。
2. Logistic 回歸
Logistic 回歸是機器學習從統計學領域借鑒過來的另一種技術。它是二分類問題的首選方法。
3. 線性判別分析
Logistic 回歸是一種傳統的分類演算法，它的使用場景僅限於二分類問題。如果你有兩個以上的類，那麼線性判別分析演算法（LDA）是首選的線性分類技術。
4.分類和回歸樹
決策樹是一類重要的機器學習預測建模演算法。
5. 樸素貝葉斯
樸素貝葉斯是一種簡單而強大的預測建模演算法。
6. K 最近鄰演算法
K 最近鄰（KNN）演算法是非常簡單而有效的。KNN 的模型表示就是整個訓練數據集。
7. 學習向量量化
KNN 演算法的一個缺點是，你需要處理整個訓練數據集。
8. 支持向量機
支持向量機（SVM）可能是目前最流行、被討論地最多的機器學習演算法之一。
9. 袋裝法和隨機森林
隨機森林是最流行也最強大的機器學習演算法之一，它是一種集成機器學習演算法。

想要學習了解更多機器學習的知識，推薦CDA數據分析師課程。CDA（Certified Data Analyst），即「CDA 數據分析師」，是在數字經濟大背景和人工智慧時代趨勢下，面向全行業的專業權威國際資格認證，旨在提升全民數字技能，助力企業數字化轉型，推動行業數字化發展。點擊預約免費試聽課。