常用演算法方法

『壹』 演算法的常用設計方法有哪些

演算法設計是一件非常困難的工作，經常採用的演算法設計技術主要有迭代法、窮舉搜索法、遞推法、貪婪法、回溯法、分治法、動態規劃法等等。
另外，為了更簡潔的形式設計和藐視演算法，在演算法設計時又常常採用遞歸技術，用遞歸描述演算法。

『貳』 常用的排序演算法都有哪些

排序演算法 所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
冒泡排序
654
比如說這個，我想讓它從小到大排序，怎麼做呢？
第一步：6跟5比，發現比它大，則交換。564
第二步：5跟4比，發現比它大，則交換。465
第三步：6跟5比，發現比它大，則交換。456

『叄』 數學中都有什麼演算法啊

定義法、配方法、待定系數法、換元法、反證法、數學歸納法、導數法、賦值法、消去法、定比分離法、比較法、分析法、綜合法 ,還有很多桑
介里有幾個比較詳細的哈.
一、換元法
「換元」的思想和方法,在數學中有著廣泛的應用,靈活運用換元法解題,有助於數量關系明朗化,變繁為簡,化難為易,給出簡便、巧妙的解答.
在解題過程中,把題中某一式子如f(x),作為新的變數y或者把題中某一變數如x,用新變數t的式子如g(t)替換,即通過令f(x)=y或x=g(t)進行變數代換,得到結構簡單便於求解的新解題方法,通常稱為換元法或變數代換法.
用換元法解題,關鍵在於根據問題的結構特徵,選擇能以簡馭繁,化難為易的代換f(x)=y或x=g(t).就換元的具體形式而論,是多種多樣的,常用的有有理式代換,根式代換,指數式代換,對數式代換,三角式代換,反三角式代換,復變數代換等,宜在解題實踐中不斷總結經驗,掌握有關的技巧.
例如,用於求解代數問題的三角代換,在具體設計時,宜遵循以下原則：（1）全面考慮三角函數的定義域、值域和有關的公式、性質；（2）力求減少變數的個數,使問題結構簡單化；（3）便於藉助已知三角公式,建立變數間的內在聯系.只有全面考慮以上原則,才能謀取恰當的三角代換.
換元法是一種重要的數學方法,在多項式的因式分解,代數式的化簡計算,恆等式、條件等式或不等式的證明,方程、方程組、不等式、不等式組或混合組的求解,函數表達式、定義域、值域或最值的推求,以及解析幾何中的坐標替換,普通方程與參數方程、極坐標方程的互化等問題中,都有著廣泛的應用.
二、消元法
對於含有多個變數的問題,有時可以利用題設條件和某些已知恆等式（代數恆等式或三角恆等式）,通過適當的變形,消去一部分變數,使問題得以解決,這種解題方法,通常稱為消元法,又稱消去法.
消元法是解方程組的基本方法,在推證條件等式和把參數方程化成普通方程等問題中,也有著重要的應用.
用消元法解題,具有較強的技巧性,常常需要根據題目的特點,靈活選擇合適的消元方法
三、待定系數法
按照一定規律,先寫出問題的解的形式（一般是指一個算式、表達式或方程）,其中含有若干尚待確定的未知系數的值,從而得到問題的解.這種解題方法,通常稱為待定系數法；其中尚待確定的未知系數,稱為待定系數.
確定待定系數的值,有兩種常用方法：比較系數法和特殊值法.
四、判別式法
實系數一元二次方程
ax2+bx+c=0 (a≠0) ①
的判別式△=b2-4ac具有以下性質：
＞0,當且僅當方程①有兩個不相等的實數根
△ ＝0,當且僅當方程①有兩個相等的實數根；
＜0,當且僅當方程②沒有實數根.
對於二次函數
y=ax2+bx+c (a≠0)②
它的判別式△=b2-4ac具有以下性質：
＞0,當且僅當拋物線②與x軸有兩個公共點；
△ ＝0,當且僅當拋物線②與x軸有一個公共點；
＜0,當且僅當拋物線②與x軸沒有公共點.
五、 分析法與綜合法
分析法和綜合法源於分析和綜合,是思維方向相反的兩種思考方法,在解題過程中具有十分重要的作用.
在數學中,又把分析看作從結果追溯到產生這一結果的原因的一種思維方法,而綜合被看成是從原因推導到由原因產生的結果的另一種思維方法.通常把前者稱為分析法,後者稱為綜合法.
六、 數學模型法
例（哥尼斯堡七橋問題）18世紀東普魯士哥尼斯堡有條普萊格河,這條河有兩個支流,在城中心匯合後流入波羅的海.市內辦有七座各具特色的大橋,連接島區和兩岸.每到傍晚或節假日,許多居民來這里散步,觀賞美麗的風光.年長日久,有人提出這樣的問題：能否從某地出發,經過每一座橋一次且僅一次,然後返回出發地?
數學模型法,是指把所考察的實際問題,進行數學抽象,構造相應的數學模型,通過對數學模型的研究,使實際問題得以解決的一種數學方法.
七、配方法
所謂配方,就是把一個解析式利用恆等變形的方法,把其中的某些項配成一個或幾個多項式正整數次冪的和形式.通過配方解決數學問題的方法叫配方法.其中,用的最多的是配成完全平方式.配方法是數學中一種重要的恆等變形的方法,它的應用十分非常廣泛,在因式分解、化簡根式、解方程、證明等式和不等式、求函數的極值和解析式等方面都經常用到它.
八、因式分解法
因式分解,就是把一個多項式化成幾個整式乘積的形式.因式分解是恆等變形的基礎,它作為數學的一個有力工具、一種數學方法在代數、幾何、三角等的解題中起著重要的作用.因式分解的方法有許多,除中學課本上介紹的提取公因式法、公式法、分組分解法、十字相乘法等外,還有如利用拆項添項、求根分解、換元、待定系數等等.
九、換元法
換元法是數學中一個非常重要而且應用十分廣泛的解題方法.我們通常把未知數或變數稱為元,所謂換元法,就是在一個比較復雜的數學式子中,用新的變元去代替原式的一個部分或改造原來的式子,使它簡化,使問題易於解決.
介里LL沒有說很詳細桑,內啥簡便演算法我也一起說了桑丶
乘法交換律,乘法分配律,加法交換律,加法結合律,乘法分配律,

『肆』 幾種常用的演算法簡介

1、窮舉法窮舉法是最基本的演算法設計策略，其思想是列舉出問題所有的可能解，逐一進行判別，找出滿足條件的解。
窮舉法的運用關鍵在於解決兩個問題：
在運用窮舉法時，容易出現的問題是可能解過多，導致演算法效率很低，這就需要對列舉可能解的方法進行優化。
以題1041--純素數問題為例，從1000到9999都可以看作是可能解，可以通過對所有這些可能解逐一進行判別，找出其中的純素數，但只要稍作分析，就會發現其實可以大幅度地降低可能解的范圍。根據題意易知，個位只可能是3、5、7，再根據題意可知，可以在3、5、7的基礎上，先找出所有的二位純素數，再在二位純素數基礎上找出三位純素數，最後在三位純素數的基礎上找出所有的四位純素數。
2、分治法分治法也是應用非常廣泛的一種演算法設計策略，其思想是將問題分解為若乾子問題，從而可以遞歸地求解各子問題，再綜合出問題的解。
分治法的運用關鍵在於解決三個問題：
我們熟知的如漢諾塔問題、折半查找演算法、快速排序演算法等都是分治法運用的典型案例。
以題1045--Square
Coins為例，先對題意進行分析，可設一個函數f(m,
n)等於用面值不超過n2的貨幣構成總值為m的方案數，則容易推導出：
f(m,
n)
=
f(m-0*n*n,
n-1)+f(m-1*n*n,
n-1)+f(m-2*n*n,
n-1)+...+f(m-k*n*n,
n-1)
這里的k是幣值為n2的貨幣最多可以用多少枚，即k=m/(n*n)。
也很容易分析出，f(m,
1)
=
f(1,
n)
=
1
對於這樣的題目，一旦分析出了遞推公式，程序就非常好寫了。所以在動手開始寫程序之前，分析工作做得越徹底，邏輯描述越准確、簡潔，寫起程序來就會越容易。
3、動態規劃法
動態規劃法多用來計算最優問題，動態規劃法與分治法的基本思想是一致的，但處理的手法不同。動態規劃法在運用時，要先對問題的分治規律進行分析，找出終結子問題，以及子問題向父問題歸納的規則，而演算法則直接從終結子問題開始求解，逐層向上歸納，直到歸納出原問題的解。
動態規劃法多用於在分治過程中，子問題可能重復出現的情況，在這種情況下，如果按照常規的分治法，自上向下分治求解，則重復出現的子問題就會被重復地求解，從而增大了冗餘計算量，降低了求解效率。而採用動態規劃法，自底向上求解，每個子問題只計算一次，就可以避免這種重復的求解了。
動態規劃法還有另外一種實現形式，即備忘錄法。備忘錄的基本思想是設立一個稱為備忘錄的容器，記錄已經求得解的子問題及其解。仍然採用與分治法相同的自上向下分治求解的策略，只是對每一個分解出的子問題，先在備忘錄中查找該子問題，如果備忘錄中已經存在該子問題，則不須再求解，可以從備忘錄中直接得到解，否則，對子問題遞歸求解，且每求得一個子問題的解，都將子問題及解存入備忘錄中。
例如，在題1045--Square
Coins中，可以採用分治法求解，也可以採用動態規劃法求解，即從f(m,
1)和f(1,
n)出發，逐層向上計算，直到求得f(m,
n)。
在競賽中，動態規劃和備忘錄的思想還可以有另一種用法。有些題目中的可能問題數是有限的，而在一次運行中可能需要計算多個測試用例，可以採用備忘錄的方法，預先將所有的問題的解記錄下來，然後輸入一個測試用例，就查備忘錄，直接找到答案輸出。這在各問題之間存在父子關系的情況下，會更有效。例如，在題1045--Square
Coins中，題目中已經指出了最大的目標幣值不超過300，也就是說問題數只有300個，而且各問題的計算中存在重疊的子問題，可以採用動態規劃法，將所有問題的解先全部計算出來，再依次輸入測試用例數據，並直接輸出答案。
4、回溯法回溯法是基於問題狀態樹搜索的求解法，其可適用范圍很廣。從某種角度上說，可以把回溯法看作是優化了的窮舉法。回溯法的基本思想是逐步構造問題的可能解，一邊構造，一邊用約束條件進行判別，一旦發現已經不可能構造出滿足條件的解了，則退回上一步構造過程，重新進行構造。這個退回的過程，就稱之為回溯。
回溯法在運用時，要解決的關鍵問題在於：
回溯法的經典案例也很多，例如全排列問題、N後問題等。
5、貪心法貪心法也是求解最優問題的常用演算法策略，利用貪心法策略所設計的演算法，通常效率較高，演算法簡單。貪心法的基本思想是對問題做出目前看來最好的選擇，即貪心選擇，並使問題轉化為規模更小的子問題。如此迭代，直到子問題可以直接求解。
基於貪心法的經典演算法例如：哈夫曼演算法、最小生成樹演算法、最短路徑演算法等。

『伍』 常用的演算法表示形式有哪些

演算法的常用表示方法有三種：

1、使用自然語言描述演算法；

2、使用流程圖描述演算法；

3、使用偽代碼描述演算法。

演算法是指對解決方案的准確、完整的描述，是解決問題的一系列清晰的指令。該演算法代表了描述解決問題的策略和機制的系統方式。也就是說，對於某個標准輸入，可以在有限的時間內獲得所需的輸出。

如果一個演算法有缺陷或不適合某個問題，執行該演算法將無法解決該問題。不同的演算法可能使用不同的時間、空間或效率來完成相同的任務。一個演算法的優劣可以用空間復雜度和時間復雜度來衡量。

『陸』 描述演算法的常用方法

1.什麼是演算法
從字面上來說，演算法也就是用於計算的方法。是用來解決某些問題的方法。通過這個方法，可以達到想要的計算結果。它就像我們小時候學些的一些數學公式和解題步驟。
演算法，一般有5個特徵：

有窮性：
演算法的執行步驟、時間、都是有限的。不會無休止的一直執行下去。
確切性：
演算法的每一步都必須有明確的定義和描述。
輸入：
一個演算法應該有相應的輸入條件，就像我們小時候做的應用題，已知什麼什麼。來求某個結果，已知部分便是輸入條件。
輸出：
演算法必須有明確的結果輸出。沒有結果，那這個演算法是沒有任何意義的。
可行性：
演算法的步驟必須是可行的，無法執行的則沒有意義，也解決不了任何問題
2.演算法的分類
按照演算法的應用來分：演算法可以分為基本演算法、幾何演算法、加密/解密演算法、查找演算法、圖標數據分析演算法等。
按照演算法的思路來分：演算法可以分為遞推演算法、遞歸演算法、窮舉演算法、分治演算法等。

下面，我們就來講我們的重點之一：也就是演算法思想：

3.常用演算法思想
窮舉演算法思想;
遞推演算法思想;
遞歸演算法思想;
分治演算法思想;
概率演算法思想;

『柒』 數值計算方法的主要研究對象有哪些其常用基本演算法主要包括哪三個方面

數值計算方法的主要研究對象：研究各種數學問題的數值方法設計、分析、有關的數學理論和具體實現。其常用基本演算法在數值分析中用到迭代法的情形會比直接法要多。例如像牛頓法、二分法、雅可比法、廣義最小殘量方法及共軛梯度法等等。在計算矩陣代數中，大型的問題一般會需要用迭代法來求解。

許多時候需要將連續模型的問題轉換為一個離散形式的問題，而離散形式的解可以近似原來的連續模型的解，此轉換過程稱為離散化。

例如求一個函數的積分是一個連續模型的問題，也就是求一曲線以下的面積若將其離散化變成數值積分，就變成將上述面積用許多較簡單的形狀（如長方形、梯形）近似，因此只要求出這些形狀的面積再相加即可。

(7)常用演算法方法擴展閱讀

數值分析也會用近似的方式計算微分方程的解，包括常微分方程及偏微分方程。

常微分方程往往會使用迭代法，已知曲線的一點，設法算出其斜率，找到下一點，再推出下一點的資料。歐拉方法是其中最簡單的方式，較常使用的是龍格－庫塔法。

偏微分方程的數值分析解法一般都會先將問題離散化，轉換成有限元素的次空間。可以透過有限元素法、有限差分法及有限體積法，這些方法可將偏微分方程轉換為代數方程，但其理論論證往往和泛函分析的定理有關。另一種偏微分方程的數值分析解法則是利用離散傅立葉變換或快速傅立葉變換。