隨機演算法與時間

Ⅰ 隨機演算法二(Randomized Algorithm)--拉斯維加斯演算法

拉斯維加斯演算法，作為一種隨機演算法，其核心在於利用隨機數進行求解。與蒙特卡洛演算法類似，它同樣是一種思想而非具體演算法。拉斯維加斯演算法在生成隨機值的過程中，會不斷嘗試，直至獲得滿意的結果。盡管可能無法生成這樣的隨機值，導致時間效率低於蒙特卡洛演算法，甚至無法得到問題解，但一旦找到解，則必然是正確解。

快速排序是一種經典的排序演算法，其輔助空間需求通常低於歸並排序。然而，傳統的快速排序存在時間復雜度不穩定的問題。通過引入拉斯維加斯演算法的思想，我們可以改進快速排序，得到一種隨機快速排序演算法，使得其時間復雜度穩定。

傳統的快速排序演算法分為兩個步驟：首先選擇一個樞軸，然後進行分割。樞軸的選擇對排序過程至關重要。通常，傳統快速排序以數組的第一個元素作為樞軸，進行分割操作。通過遞歸處理分割後的數組，最終得到一個有序數組。

快速排序的時間復雜度與分割次數密切相關。為了降低分割次數，可以優化樞軸的選擇，例如查找數組的中值作為樞軸。這樣，分割後的兩個子問題規模相等，從而降低時間復雜度。然而，由於中值查找演算法時間復雜度較高，實際應用中，演算法表現效果可能不如歸並排序。

為了進一步優化快速排序，我們可以採用隨機快速排序演算法。該演算法在樞軸選擇上進行了優化，隨機選擇一個滿足特定條件的樞軸。通過分析「好樞軸」和「壞樞軸」的概念，我們可以得出演算法的期望時間復雜度。在最壞情況下，每次隨機選擇的好樞軸都正好是最小或最大的元素，演算法時間復雜度的遞歸式可以表示為：

通過畫遞歸樹的方法求解，我們可以得出演算法的期望時間復雜度為O(nlogn)。

以上內容參考自MIT 6.046J。

Ⅱ MATLAB | 時間序列預測 | 隨機森林演算法 | 附數據和出圖代碼 | 直接上手

探索MATLAB中隨機森林演算法在時間序列預測的應用，下面內容將詳細闡述基本定義與出圖效果，並提供直接獲取開源代碼的鏈接。

隨機森林時序預測演算法是一種基於隨機森林的時間序列預測方法，其核心在於通過構建多個決策樹模型，對輸入數據進行預測。這種演算法通過隨機選取樣本和特徵，減少過擬合風險，提升模型泛化能力。

直觀展示隨機森林時序預測演算法效果的圖表如下：

為了更深入理解隨機森林時序預測的過程，觀看以下視頻教程，獲取操作指南：

MATLAB環境下的隨機森林時序預測開源代碼，直接獲取方式如下：

mbd.pub/o/bread/ZJiTmJt...

探索更多時序預測方案，包括但不限於4種、5種和9種全家桶細節，參見以下鏈接：

mbd.pub/o/bread/ZJiTmJx...

mbd.pub/o/bread/ZJaXlJt...

mbd.pub/o/bread/ZJiTmJx...

在代碼實現過程中遇到任何疑問，歡迎參與學術討論，共同探討科研、寫作、代碼等話題，攜手前進。

Ⅲ 微信紅包的隨機演算法是怎樣實現的

我們在一個20人的群中，自己發紅包以及結合其他人發出紅包的情況，整合成兩輪的數據。每次金額設置都是20塊並且有20個，第一輪是發了15次，第二輪是發了19次，總結成表格，然後為了避免突發的數據影響判斷，我們將兩輪數據雜糅從而生成了其他的三輪數據，一共是五輪數據。羅列如下表，高亮的數據為最佳手氣。每一列的數據最早搶到紅包的在最底端，越往上越晚搶。
從所有黃色的數值（最佳手氣金額）可看出，所有最佳手氣值都在平均值*2的前後附近（平均值=總金額/紅包總個數，這里平均值=20/20=1），事實上確實如此，可通過微信紅包分發演算法得到驗證，演算法具體見後文
然後我們選取部分數據開始製作散點圖。橫軸為1-20，分別表示搶到紅包的人的編號，隨遞增而越早。也就是20代表最早搶到的人。縱軸為金額。同樣的形狀顏色的點代表一次發紅包，然後我們抓取部分數據顯示為散點圖，越密集代表該順序位的用戶得到的金額越穩定。散點圖如下：

規律一：我們可以看到，所有紅包大多數金額分布在0.5到1.5元之間，顯示為圖中方框所示，大部分點都分布在這個位置。然後是順序位密集程度的對比，可以發現20、19，也就是最先搶到紅包的人，小圓圈所示基本的點都集中在小范圍，說明先搶紅包的人得到的金額會比較穩定，但同時最佳手氣的概率也比較低。大圓圈所示的是極不穩定，飄忽的金額分布，表示越晚搶紅包得到的金額會飄忽不穩，但同時，搶到最佳手氣等大金額的紅包概率也比早搶的高。
根據上面的分析，我們又寫了一個過濾計數函數，針對金額的分段的紅包個數進行統計：
比如2.0-2.5
得到如下金額分布：
折線圖：
規律二：絕大多數的紅包的金額都集中在1-1.5，也就是說20塊錢發20個紅包的金額分布集中在比平均數大一點點的附近，同時較大幅超過平均數金額的紅包大大少於低於於平均數的紅包數量。
那我們繼續擴大數據的規模，將幾輪數據的均值和標准差分別做成折線圖：
綜合上面各個折線圖的情況，我們可以得到越早搶紅包的標准差越小，越晚搶紅包的標准差越大，但同時，由均值和總額可以看出來，越早搶紅包的均值往往要更高，紅包金額得到最佳手氣概率也會相對較小，越晚搶紅包的人則得到最佳手氣等大手氣的概率更大。
為了得到更為趨近規律的曲線和規律，我們決定將兩輪真實數據合並起來，然後給出冪函數的趨近線（虛線），如下圖：
由於均值受極值波動影響較大，所以我們去除一些因為偶然差產生的極端點（圓圈的點）從而發現是遞增的趨勢。
規律三：可以很明顯的看到，均值是隨著搶紅包的越晚而緩慢遞減，標准差值同時也往上遞增，這個趨勢結合之前的分析，我們猜想，即標准差越大說明，領取到最大的紅包和最小紅包的風險越大，也就是說越晚搶標准差越大，對於冒險主義者來講是最好的，因為他有很大概率獲得最大的金額，但也大概率獲得最小的紅包，風險與收益並存；均值越大，說明每次都拿到一個不大不小的紅包，雖然獲得最小和最大金額紅包的概率很小，但起碼不虧本，也就是說越早搶，均值越穩定，這比較適合不喜歡冒險的人。
驗證預測結果：
21：24分發送預測結果到另一位同學微信：

隨後開始發紅包：

結果：
最佳手氣為第8個人且金額為1.13
與預測結果一致，規律基本正確！
總結：
（1）最佳手氣為1.13塊，根據我們推導的預測公式=總額/紅包總個數*2*隨機數（0-2的double數）, 也就是說最佳手氣在總額/紅包總個數*2值的前後附近。這里我們判斷在0.8-1.3之間，推斷正確
（2)平均值為0.5元，0.5-0.8元的紅包有3個，小於0.5的紅包有6個，說明大於平均值的紅包個數多於小於平均值的個數。與我們的第二點預測完全正確
(3)最佳手氣位置：根據我們的散點圖發現，最先搶到紅包的人，得到的金額會比較穩定，但同時最佳手氣的概率也比較低。表示越晚搶紅包得到的金額波動較大，但同時搶到最佳手氣等大金額的紅包概率也比早搶的高。所以我們推斷，最佳手氣位置在最後20%-30%之間。
微信紅包隨機分發演算法c＋＋模擬：
基本思路：每次搶到一個紅包金額等於：紅包剩餘金額/紅包剩餘個數*2*隨機數（0-1的double型），如果計算的結果小於等於0.01，則取0.01值
主要代碼：
double packages[50000];
double Luckiest_money=0;
void getPackage(int remainSize,double remainMoney){
srand((unsigned)time(NULL));
for(int i=0;i