序列數據處理演算法

⑴ 對一個數據序列，設計一個演算法計算它們的最大值和最小值

可以用遞歸的思想計算。例如，計算最大值，如果數據序列只有一個值，則取這個值本身；如果只有兩個值，則取這兩個值的最大值；如果超過兩個值，則把序列分成元素個數相近的兩組，分別取它們的最大值，然後在這兩個值中再取最大值。最小值也可以用同樣的遞歸方法。

⑵ 如何進行海量數據排序,有哪些流行方法

你問的是關於對於海量數據排序的演算法？工具？
1 排序演算法：①就時間性能而言：數據序列基本正序(基本接近期望結果)時,直接插入排序、冒泡排序最好；數據序列基本逆序(基本與期望結果相反)時，歸並排序、堆排序較好，快速排序次之，冒泡排序、直接插入排序最差；數據序列分布比較隨機時的平均時間性能快速排序最佳；②就空間開銷而言，歸並排序的空間開銷最多；③就演算法復雜程度而言，冒泡排序、直接插入排序的實現最簡單；
2 排序工具：推薦使用資料庫系統，特別是Oracle、DB2、SQL Server等，容量大、速度快、功能強、安全性高，當然價格也上去了。流行的DBMS主要有Oracle、DB2、SQL Server、Sybase、MySql、VF、Access等，各有千秋。

⑶ 數據挖掘演算法的演算法分類

C4.5就是一個決策樹演算法，它是決策樹（決策樹也就是做決策的節點間像一棵樹一樣的組織方式，其實是一個倒樹）核心演算法ID3的改進演算法，所以基本上了解了一半決策樹構造方法就能構造它。決策樹構造方法其實就是每次選擇一個好的特徵以及分裂點作為當前節點的分類條件。C4.5比ID3改進的地方時：
ID3選擇屬性用的是子樹的信息增益（這里可以用很多方法來定義信息，ID3使用的是熵（entropy）（熵是一種不純度度量准則）），也就是熵的變化值，而C4.5用的是信息增益率。也就是多了個率嘛。一般來說率就是用來取平衡用的，就像方差起的作用差不多，比如有兩個跑步的人，一個起點是100m/s的人、其1s後為110m/s；另一個人起速是1m/s、其1s後為11m/s。如果僅算差值那麼兩個就是一樣的了；但如果使用速度增加率（加速度）來衡量，2個人差距就很大了。在這里，其克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足。在樹構造過程中進行剪枝，我在構造決策樹的時候好討厭那些掛著幾個元素的節點。對於這種節點，乾脆不考慮最好，不然很容易導致overfitting。對非離散數據都能處理，這個其實就是一個個式，看對於連續型的值在哪裡分裂好。也就是把連續性的數據轉化為離散的值進行處理。能夠對不完整數據進行處理，這個重要也重要，其實也沒那麼重要，缺失數據採用一些方法補上去就是了。 (樸素貝葉斯NB)
NB認為各個特徵是獨立的，誰也不關誰的事。所以一個樣本（特徵值的集合，比如「數據結構」出現2次，「文件」出現1次），可以通過對其所有出現特徵在給定類別的概率相乘。比如「數據結構」出現在類1的概率為0.5，「文件」出現在類1的概率為0.3，則可認為其屬於類1的概率為0.5*0.5*0.3。 (支持向量機SVM)
SVM就是想找一個分類得最」好」的分類線/分類面（最近的一些兩類樣本到這個」線」的距離最遠）。這個沒具體實現過，上次聽課，那位老師自稱自己實現了SVM，敬佩其鑽研精神。常用的工具包是LibSVM、SVMLight、MySVM。 (Mining frequent patterns without candidate generation)
這個也不太清楚。FP-growth演算法(Frequent Pattern-growth)使用了一種緊縮的數據結構來存儲查找頻繁項集所需要的全部信息。採用演算法：將提供頻繁項集的資料庫壓縮到一棵FP-tree來保留項集關聯信息，然後將壓縮後的資料庫分成一組條件資料庫（一種特殊類型的投影資料庫），每個條件資料庫關聯一個頻繁項集。 K-Means是一種最經典也是使用最廣泛的聚類方法，時至今日扔然有很多基於其的改進模型提出。K-Means的思想很簡單，對於一個聚類任務（你需要指明聚成幾個類，當然按照自然想法來說不應該需要指明類數，這個問題也是當前聚類任務的一個值得研究的課題），首先隨機選擇K個簇中心，然後反復計算下面的過程直到所有簇中心不改變（簇集合不改變）為止：步驟1：對於每個對象，計算其與每個簇中心的相似度，把其歸入與其最相似的那個簇中。
步驟2：更新簇中心，新的簇中心通過計算所有屬於該簇的對象的平均值得到。
k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇k 個對象作為初始聚類中心；而對於所剩下其它對象，則根據它們與這些聚類中心的相似度（距離），分別將它們分配給與其最相似的（聚類中心所代表的）聚類；然後再計算每個所獲新聚類的聚類中心（該聚類中所有對象的均值）；不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。 BIRCH也是一種聚類演算法，其全稱是Balanced Iterative Recing and Clustering using Hierarchies。BIRCH也是只是看了理論沒具體實現過。是一個綜合的層次聚類特徵(Clustering Feature, CF)和聚類特徵樹(CF Tree)兩個概念，用於概括聚類描述。聚類特徵樹概括了聚類的有用信息，並且佔用空間較元數據集合小得多，可以存放在內存中，從而可以提高演算法在大型數據集合上的聚類速度及可伸縮性。
BIRCH演算法包括以下兩個階段：
1）掃描資料庫，建立動態的一棵存放在內存的CF Tree。如果內存不夠，則增大閾值，在原樹基礎上構造一棵較小的樹。
2）對葉節點進一步利用一個全局性的聚類演算法，改進聚類質量。
由於CF Tree的葉節點代表的聚類可能不是自然的聚類結果，原因是給定的閾值限制了簇的大小，並且數據的輸入順序也會影響到聚類結果。因此需要對葉節點進一步利用一個全局性的聚類演算法，改進聚類質量。 AdaBoost做分類的一般知道，它是一種boosting方法。這個不能說是一種演算法，應該是一種方法，因為它可以建立在任何一種分類演算法上，可以是決策樹，NB，SVM等。
Adaboost是一種迭代演算法，其核心思想是針對同一個訓練集訓練不同的分類器(弱分類器)，然後把這些弱分類器集合起來，構成一個更強的最終分類器(強分類器)。其演算法本身是通過改變數據分布來實現的，它根據每次訓練集之中每個樣本的分類是否正確，以及上次的總體分類的准確率，來確定每個樣本的權值。將修改過權值的新數據集送給下層分類器進行訓練，最後將每次訓練得到的分類器最後融合起來，作為最後的決策分類器。使用adaboost分類器可以排除一些不必要的訓練數據，並將關鍵放在關鍵的訓練數據上面。 GSP，全稱為Generalized Sequential Pattern(廣義序貫模式)，是一種序列挖掘演算法。對於序列挖掘沒有仔細看過，應該是基於關聯規則的吧！網上是這樣說的：
GSP類似於Apriori演算法，採用冗餘候選模式的剪除策略和特殊的數據結構-----哈希樹來實現候選模式的快速訪存。
GSP演算法描述:
1）掃描序列資料庫，得到長度為1的序列模式L1，作為初始的種子集。
2）根據長度為i 的種子集Li ，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然後掃描序列資料庫，計算每個候選序列模式的支持度，產生長度為i+1的序列模式Li+1，並將Li+1作為新的種子集。
3）重復第二步，直到沒有新的序列模式或新的候選序列模式產生為止。
產生候選序列模式主要分兩步：
連接階段：如果去掉序列模式s1的第一個項目與去掉序列模式s2的最後一個項目所得到的序列相同，則可以將s1與s2進行連接，即將s2的最後一個項目添加到s1中。
修切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。
候選序列模式的支持度計算：對於給定的候選序列模式集合C，掃描序列資料庫，對於其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，並增加其支持度計數。 又是一個類似Apriori的序列挖掘。
其中經典十大演算法為：C4.5，K-Means，SVM，Apriori，EM，PageRank，AdaBoost，KNN，NB和CART。

⑷ 用冒泡排序演算法對數據序列(49,38,65,97,76,134,27,49)

思路解析：（49，38，65，97，76，13，27）→（38，49，65，76，13，27，97）→（38，49，65，13，27，76，97） 答案：2

⑸ 數據的演算法都有哪些……

A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的 NPC的移動計算，或線上游戲的 BOT的移動計算上。該演算法像 Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於 人工智慧領域,1976 年Lowerre在其稱為 HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。

Branch and bound
分支定界演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。

數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。

Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。

動態規劃
動態規劃是一種在 數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。 動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。

歐幾里得演算法
在 數學中，輾轉相除法，又稱 歐幾里得演算法，是求 最大公約數的演算法。輾轉相除法首次出現於 歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至 東漢出現的《九章算術》。

快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。

哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該 函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列 函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。

堆排序
Heapsort是指利用堆積樹（堆）這種 數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。

歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計 數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經 專利失效，其被廣泛地用於 電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。

並查集Union-find
並查集是一種樹型的 數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm
尋找最可能的隱藏狀態序列
等等這些，演算法很多。

⑹ 時間序列分析的具體演算法

用隨機過程理論和數理統計學方法，研究隨機數據序列所遵從的統計規律，以用於解決實際問題。由於在多數問題中，隨機數據是依時間先後排成序列的，故稱為時間序列。它包括一般統計分析（如自相關分析、譜分析等），統計模型的建立與推斷，以及關於隨機序列的最優預測、控制和濾波等內容。經典的統計分析都假定數據序列具有獨立性，而時間序列分析則著重研究數據序列的相互依賴關系。後者實際上是對離散指標的隨機過程的統計分析，所以又可看作是隨機過程統計的一個組成部分。例如,用x(t)表示某地區第t個月的降雨量，{x(t)，t=1，2，…}是一時間序列。對t=1，2，…，T，記錄到逐月的降雨量數據x(1)，x(2)，…，x(T)，稱為長度為T的樣本序列。依此即可使用時間序列分析方法，對未來各月的雨量x(T+l)(l=1,2,…)進行預報。時間序列分析在第二次世界大戰前就已應用於經濟預測。二次大戰中和戰後，在軍事科學、空間科學和工業自動化等部門的應用更加廣泛。
就數學方法而言，平穩隨機序列（見平穩過程）的統計分析，在理論上的發展比較成熟，從而構成時間序列分析的基礎。
頻域分析 一個時間序列可看成各種周期擾動的疊加，頻域分析就是確定各周期的振動能量的分配，這種分配稱為「譜」，或「功率譜」。因此頻域分析又稱譜分析。譜分析中的一個重要是統計量,稱為序列的周期圖。當序列含有確定性的周期分量時，通過I(ω)的極大值點尋找這些分量的周期，是譜分析的重要內容之一。在按月記錄的降雨量序列中，序列x(t)就可視為含有以12為周期的確定分量，所以序列x(t)可以表示為 ,它的周期圖I(ω)處有明顯的極大值。
當平穩序列的譜分布函數F（λ）具有譜密度ƒ(λ)（即功率譜）時，可用(2π)-1I(λ)去估計ƒ(λ)，它是ƒ(λ)的漸近無偏估計。如欲求ƒ(λ)的相合估計（見點估計），可用I(ω)的適當的平滑值去估計ƒ(λ),常用的方法為譜窗估計即取ƒ(λ)的估計弮(λ)為 ,式中wt(ω)稱為譜窗函數。譜窗估計是實際應用中的重要方法之一。譜分布F(λ)本身的一種相合估計可由I(ω)的積分直接獲得，即 。研究以上各種估計量的統計性質，改進估計方法，是譜分析的重要內容。時域分析 它的目的在於確定序列在不同時刻取值的相互依賴關系,或者說,確定序列的相關結構。這種結構是用序列的自相關函0,1,…)來描述的,為序列的自協方差函數值,m=Ex(t)是平穩序列的均值。常常採用下列諸式給出m，γ(k),ρ(k)的估計： ,通(k)了解序列的相關結構,稱為自相關分析。研究它們的強、弱相合性及其漸近分布等問題，是相關分析中的基本問題。模型分析 20世紀70年代以來，應用最廣泛的時間序列模型是平穩自回歸-滑動平均模型 (簡稱ARMA模型)。其形狀為： 式中ε(t)是均值為零、方差為σ2的獨立同分布的隨機序列;和σ2為模型的參數,它們滿足： 對一切|z|≤1的復數z成立。p和q是模型的階數，為非負整數。特別當q=0時，上述模型稱為自回歸模型；當p=0時, 稱為滑動平均模型。根據x(t)的樣本值估計這些參數和階數，就是對這種模型的統計分析的內容。對於滿足ARMA模型的平穩序列，其線性最優預測與控制等問題都有較簡捷的解決方法,尤其是自回歸模型,使用更為方便。G.U.尤爾在1925～1930年間就提出了平穩自回歸的概念。1943年,Η.Β.曼和Α.瓦爾德發表了關於這種模型的統計方法及其漸近性質的一些理論結果。一般ARMA模型的統計分析研究，則是20世紀60年代後才發展起來的。特別是關於p，q值的估計及其漸近理論，出現得更晚些。除ARMA模型之外,還有其他的模型分析的研究,其中以線性模型的研究較為成熟，而且都與ARMA模型分析有密切關系。回歸分析 如果時間序列x(t)可表示為確定性分量φ(t)與隨機性分量ω(t)之和，根據樣本值x(1)，x(2)，…,x(T)來估計φ(t)及分析ω(t)的統計規律，屬於時間序列分析中的回歸分析問題。它與經典回歸分析不同的地方是，ω(t)一般不是獨立同分布的，因而在此必須涉及較多的隨機過程知識。當φ(t)為有限個已知函數的未知線性組合時，即 ，式中ω(t)是均值為零的平穩序列,α1,α2,…,αs是未知參數,φ1(t),φ2(t),…,φs(t)是已知的函數,上式稱為線性回歸模型，它的統計分析已被研究得比較深入。前面敘述的降雨量一例，便可用此類模型描述。回歸分析的內容包括:當ω(t)的統計規律已知時，對參數α1,α2,…,αs進行估計,預測x(T+l)之值；當ω(t)的統計規律未知時，既要估計上述參數，又要對ω(t)進行統計分析，如譜分析、模型分析等。在這些內容中,一個重要的課題是:在相當廣泛的情況下，證明 α1,α2,…,αs的最小二乘估計，與其線性最小方差無偏估計一樣，具有相合性和漸近正態分布性質。最小二乘估計姙j(1≤j≤s)不涉及ω(t)的統計相關結構，是由數據x(1)，x(2)，…，x(T)直接算出，由此還可得(t)進行時間序列分析中的各種統計分析，以代替對ω(t)的分析。在理論上也已證明，在適當的條件下，這樣的替代具有滿意的漸近性質。由於ω(t)的真值不能直接量測，這些理論結果顯然有重要的實際意義。這方面的研究仍在不斷發展。
時間序列分析中的最優預測、控制與濾波等方面的內容見平穩過程條。近年來多維時間序列分析的研究有所進展，並應用到工業生產自動化及經濟分析中。此外非線性模型統計分析及非參數統計分析等方面也逐漸引起人們的注意。

⑺ 一維實序列的快速傅里葉變換（FFT）

通過前面的分析，我們認識到傅里葉變換本身是復數運算，地球物理獲取的數據大多數是實數，對於實數的變換原則上可直接套用復序列的FFT演算法，但那樣是把實數序列當作虛部為零的復數對待，顯然需要存儲虛部的零並進行無功的運算，既浪費了一倍的計算內存，又降低了約一半的運算速度。

為了不浪費不可不設的虛部內存和必然出現的復數運算，可否將一個實序列分為兩個子實序列，分別作為實部與虛部構成一個復數序列，然後用復序列的FFT演算法求其頻譜，對合成的復序列頻譜進行分離和加工得到原實序列的頻譜呢？答案是肯定的，實現這一過程思路就是實序列FFT演算法的基本思想。

1.實序列的傅里葉變換性質

對於一個N個樣本的實序列x（k），其頻譜為X（j），用X_r（j）和X_i（j）表示X（j）的實部和虛部， 表示X（j）的共軛，則

證明：已知 則

地球物理數據處理基礎

上式兩端取共軛，並注意到x（k）是實序列，則

地球物理數據處理基礎

這就是實序列的傅里葉變換具有復共軛性。

其同樣具有周期性，即

地球物理數據處理基礎

2.一維實序列的FFT演算法

（1）同時計算兩個實序列的FFT演算法

已知兩個實序列h（k），g（k）（k＝0，1，…，N－1），例如重磁異常平面數據中的兩條剖面，或地震勘探中的兩道地震記錄，可以人為地構成一個復序列：

地球物理數據處理基礎

設h（k）的頻譜為H（j）＝H_r（j）＋iH_i（j）

g（k）的頻譜為G（j）＝G_r（j）＋iG_i（j）

y（k）的頻譜為Y（j）＝Y_r（j）＋i Y_i（j）

利用上節的復序列FFT演算法，求得Y（j），即Y_r（j）和Y_i（j）已知，來尋找H_r（j），H_i（j），G_r（j），G_i（j）與Y_r（j），Y_i（j）之間的關系。

對式（8－22）作傅里葉變換：

地球物理數據處理基礎

由於H（j），G（j）本身是復序列，所以不能僅從上式分離出H（j）和G（j）。應用Y（j）的周期性，容易得到

Y（N－j）＝H（－j）＋iG（－j）

上式取共軛：

地球物理數據處理基礎

由於h（k），g（k）為實序列，對上式右端應用復共軛定理，得

地球物理數據處理基礎

對式（8－23）展開，得

地球物理數據處理基礎

對式（8－24）展開，並應用共軛關系，得

地球物理數據處理基礎

把式（8－25）和式（8－26）與Y（j）＝Y_r（j）＋iY_i（j）進行對比，有

地球物理數據處理基礎

整理得

地球物理數據處理基礎

因此，對於兩個實序列，通過構造一個復序列，應用復序列的FFT演算法和式（8－28）的分離加工，即可得到兩個實序列的頻譜。

（2）計算2 N個數據點的實序列FFT演算法

設有2N點的實序列u（k）（k＝0，1，…，2N－1），首先按k的偶、奇分成兩個子實序列，並構成復序列，即

地球物理數據處理基礎

通過調用復序列FFT演算法，求得y（k）的頻譜為Y（j）。另記h（k），g（k）的頻譜為H（j）和G（j）。

利用前面式（8－23）和式（8－24），容易求得

地球物理數據處理基礎

下面分析用H（j），G（j）形成u（k）頻譜的問題。記u（k）（k＝0，1，…，2 N－1）的頻譜為V（j），分析V（j），H（j），G（j）之間的關系，根據定義

地球物理數據處理基礎

利用式（8－31）和式（8－34）可換算出u（k）的前N個頻譜V（j）（j＝0，1，…，N－1），還要設法求u（k）的後N個頻譜V（N＋j）（j＝0，1，…，N－1）。利用實序列其頻譜的復共軛和周期性：

（1）H（N）＝H（0），G（N）＝G（0），W^N₁＝－1，得

地球物理數據處理基礎

（2）由於u（k）（k＝0，1，…，2N－1）是實序列，同樣利用實序列其頻譜的復共軛和周期性，用已求出的前N個頻譜V（j）表示出後面的N－1個頻譜V（N＋j）：

地球物理數據處理基礎

由於0<2N－j<N，所以可從V（j）（j＝0，1，…，N－1）中選出V（2N－j）（j＝N＋1，N＋2，…，2 N－1），並直接取其共軛 即可得到V（N＋1）～V（2 N－1），從而完成整個實序列頻譜的計算。

總結以上敘述，一維實序列u（k）（k＝0，1，…，2N－1）的FFT計算編程步驟如下：

（1）按偶、奇拆分實序列u（k），並構造復序列：

地球物理數據處理基礎

（2）調用復序列的FFT計算y（k）的頻譜Y（j）（j＝0，1，…，N－1）；

（3）用下式計算形成h（k），g（k）的頻譜H（j）和G（j）；

地球物理數據處理基礎

（4）用下式換算實序列u（k）的頻譜V（j）（j＝0，1，…，2 N－1）：

地球物理數據處理基礎

［例3］求實序列樣本u（k）＝｛1，2，1，1，3，2，1，2｝（k＝0，1，…，7）的頻譜。

解：按偶、奇拆分實序列u（k），按式（8－37）構造復序列c（j）（j＝0，1，2，3），即

c（0）＝1＋2i； c（1）＝1＋i； c（2）＝3＋2i； c（3）＝1＋2i。

（1）調用復序列FFT求c（j）（j＝0，1，2，3）的頻譜Z（k）（k＝0，1，2，3），得

Z（0）＝6＋7i； Z（1）＝－3； Z（2）＝2＋i； Z（3）＝－1。

地球物理數據處理基礎

（3）運用公式（8－38）計算H（j），G（j）：

地球物理數據處理基礎

（4）根據式（8－39）求出u（k）（k＝0，1，…，7）的8個頻譜V（j）（j＝0，1，…，7）：

地球物理數據處理基礎

地球物理數據處理基礎

由上例可見，完成全部2 N個實序列頻譜的計算只需做N次FFT計算，相比直接用復序列的FFT演算法節省了約一半的計算量。

⑻ 將一組無序的數據排列成一個有序序列，寫一算 法實現。並分析該演算法的時間復雜度。

#include "stdio.h"
int main()
{
int a[100],n,i,j,k,tmp;
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%d",&a[i]);
for(i=0;i<n;i++)//選擇排序,兩重循環,復雜度O(n*n)
{
k=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[k])k=j;
}
tmp=a[i];
a[i]=a[k];
a[k]=tmp;
}
for(i=0;i<n;i++)printf("%d ",a[i]);
puts("");
return 0;
}

⑼ 消除冗餘序列演算法

main()
{
int a[100];
int i, t,b,c;
printf("please enter 100 number.");
do
{
for(i=0;i<100;i++)
{scanf("%d",a[i]);
if(a[i]!=0||a[i]!=1)
{
break;printf("error,please enter again!");
}
else
t=0;
}
} while (t=0) ;

b=strlen(a);

for(i=b,c=1;i>0;i--)
{if (a[i]==a[i-1]==1)
c+=1;
else
break;
}
if(c>=3)
{
a[b]=2;
for(i=1;i<=c;i++)
a[b-i]=0;
a[b-c]=1;
}

for(i=0,c=0;i<b;i++)
{if(a[i]==a[i+1]==1)
c+=1;
else
break;
}
if(c>=3)
{for(i=0;i<=c;i++)
{a[i+1]=a[i];a[i+1]=0;}
a[i]=1;
a[c+1]=2;
}

}
我用的是WIN-TC遍的
已經測試過
可以通過
你可以試試

⑽ 序列比對的演算法有哪些在應用上各有何特點

首先你要明白——Clustalx的多序列比對演算法是基於雙序列比對的，它先將所有序列兩兩比對，然後根據兩兩比對結果構建指導樹，再根據指導樹依次添加相似度最高的