有哪些演算法是中國人自己創造的？

12-30

今天偶然了解到cdq分治是一個女高中生搞出來的。覺得很驚訝，之前一直以為是一個比較古老的演算法。所以就想了解一下還有哪些演算法是中國人自己搞出來的。我知道的除了cdq分治就只有莫隊演算法了

一堆回答『SPFA』的人是要哪樣？。。

Wikipedia說的很清楚，這種優化是在1970年就被Yen提出了，並且不會改進最壞複雜度。

以及『SLF』之類的所謂『優化』是會被卡到指數複雜度的。

作為OIer，也要有點理論常識。。

（看到很多人回答了數學相關的演算法，我也來說一個。高斯消元法約公元179年在《九章算術》中就出現了。）

========2017.08.13 21:55:24 update========

居然被排到了第一，有些不知所措，看來得多寫一些東西了。

有名的都被說過了，我來說一些OI中出現的，比較有名的，有可能是新東西的演算法/數據結構。

相關問題：有哪些演算法或數據結構是ACM大牛們在比賽中創造出來的？

陳立傑，後綴平衡樹。試圖找過英文資料然而並沒有找到相同的數據結構，不知是否有人知道。
黃嘉泰，使用可持久化線段樹解決範圍選擇查詢。根據上面鏈接 @顧昱洲的回答，這很可能是個新的演算法。
呂凱風，動態仙人掌。
莫濤，莫隊演算法（查詢分塊）。能用 $O(N sqrt Q cdot F)$ 時間離線回答所有查詢。據說有類似的東西，但似乎沒有人整理過這個方法及其衍生版本。國外有不少人使用這個名字（Mo"s algorithm），也有人堅持認為應該叫query square root decomposition。
任之洲， $O(frac{n^{frac 3 4}}{log n})$ 求積性函數前綴和的演算法。

cdq分治就是分治的一種特殊應用，而且這種應用肯定也在很久以前就有了。

我一般並不使用cdq分治這個稱呼，因為我們沒有必要尋找每一道分治題目和cdq論文中例題的關聯然後再給它按上cdq分治這一稱號（並且現在有不少對分治一知半解的人見到分治題就說是cdq分治），cdq本人在論文中也使用的是「分治」一詞而不是「cdq分治」。

我第一眼看到的時候就被圈粉了。

聽好了，

中國剩餘定理！

aqx搜索，以極大的腦迴路為核心，常用於一般搜索無法AC的題目，且速度常常遠比正解還快，由某知名中學的信息學競賽信息學教練提出並完善，對於一般題目可以將2的n次方的搜索轉化為小於n平方的複雜度。目前該演算法發明人正撰寫論文，有望獲得國際社會的一致認可，且在全國ACM與OI界中逐漸推廣。@艾慶興

Update：已刪去SPFA。

Chu-Liu algorithm, or Edmonds" algotirhm.給出了有向圖中最小生成樹的生成方案，兩個幾乎等價的方法分別在1965年由Yoeng-Jin Chu與Tseng-Hong Liu與1967年由Jack Edmonds獨立提出。這可能是中國人在計算機科學近現代演算法研究領域中提出的第一個可能也是至今為止最為著名的一個經典演算法。（如若有誤懇請指出）

Zhu-Takaoka string matching algorithm, 是關於著名的Boyer-Moore string search algorithm的一個變體。於1987年由Rui-Feng Zhu與T. Takaoka發表。

Xiaolin Wu"s line algorithm, 是計算機圖形學中線段生成中的一個anti-aliasing演算法。是重要的Bresenham"s algorithm的一個有力的競爭對手。於1991年由Xiaolin Wu發表，隨後她也發表了該方法在圓上的拓展。

Wang and Lanudau algorithm，於2001年由Fugao Wang與David P. Lanudau提出。是一個重要的用於計算系統中density of states的蒙特卡羅方法。

限於學識所知不多，之所以回答這個問題是之前接觸到dependency parsing中MST方法時驚喜地發現有向圖中的MST（一般稱作最小樹形圖，畢竟二者還是有相當的差異）竟然是由中國人最早在五十多年前提出的。

這也讓我回想起高中準備化學競賽時翻閱name reaction發現黃鳴龍先生在1946年改進提出的Wolff-Kishner-黃鳴龍還原，而那也是第一個以中國人名字命名的有機化學反應，厚厚一本name reaction，竟也再找不到二三個中國人名。（有必要一提於1996年由史教授發展的Shi Epoxidation—史氏環氧化反應，可能是目前認可度最高的以中國人命名的name reaction）

很遺憾的是，在五六十年前先輩開創先河後，由於種種歷史原因華人沒有能趕上黃金時代的浪潮。時至今日，我輩研究人員應當慶幸所處之時代與更加之發奮圖強在新的一波又一波浪潮之中尋覓自己的一份價值。

不是還有一個朱劉演算法嗎，之前刷生成樹專題發現的，求最小樹形圖的(雖然作者具體名字記不清了)

買6塊錢的東西給收銀員10+1塊

秦九韶演算法。

將n次多項式函數的求值由 ${O} ( n^{2})$ 優化到 ${O} ( n )$ 。

最正規的大概是最小樹形圖的朱劉演算法數學家發明的演算法

還有名字很吊的中國剩餘定理很數學的演算法

求區間眾數的莫隊演算法應該是發明（未考證）但適用範圍小點

Cdq分治和spfa最短路是已經存在的演算法優化挪用到acm/oi里不算髮明創造

1、「吳法」：吳法是由吳文俊院士所創，主要解決非線性方程組的解析求解，非線性方程組的數值求解可視為某種「梯度下降法」的變形，但是解析求解卻難以找到統一的演算法，「吳法」就是解決這一問題的統一的方法之一，它也可能是求解非線性方程組的唯一的統一的方法，這種方法對於平面幾何、立體幾何的證明尤為有效，核心是將幾何問題先變為多項式代數表示，然後整序，逐步消元，得到一個方程式，這個代數方程式等價於要證明的幾何問題的結論。吳院士的演算法將這個過程標準化、統一化，這樣就能通過計算機自動實現。這就是吳法的意義。

2、辛幾何演算法：辛幾何演算法由馮康院士所創，主要解決非線性方程的數值求解問題，對於非線性方程，一般用差分方法，當然還有其他的方法，馮院士構造了一種新的差分格式，即所謂的辛格式，這種格式在迭代過程中保辛，大約可以理解成「保面積」、「保功」，特別是時間增量較大時，計算時精度損失較小。構造辛格式是問題的難點，關鍵是要找到問題的一對對偶變數，後來鍾萬勰院士將這種演算法推廣到結構力學、結構動力學、控制理論等方面問題的求解。如上方法的基礎都是自然界的哈密頓原理、勒降德原理的具體體現。

我就知道主席樹和動態仙人掌（但是主席樹好像就是可持久化線段樹？

突然想到了梁友棟演算法

在學習圖形學窗口裁剪有關演算法時候

記得老師激動的說了一句，講了這麼多終於有一個跟我們中國有關係的演算法了

放一個鏈接吧，有興趣的可以看一下

http://m.blog.csdn.net/daisy__ben/article/details/51941608

也順便紀念一下逝去的大學生涯

也記住那位講課的周老師

Upack壓縮PE頭的演算法，當時幾乎所有PE Viewer束手無策甚至崩潰退出，即使放在現在看也是天才一般的思路。

作者是中國人dwing。

很多oi/acm界名氣較大的演算法，比如題主提到的cdq分治，以及其他答主提到的spfa等演算法，都是已經存在的演算法或者一種演算法的特定運用方式被介紹到oi/acm中來。感覺說發明是有些牽強的。

朱劉演算法應該確實是我國兩位數學家發明的全新演算法。

不保證我說的都正確，等大神考據

這個問題下面大多數都是oi/acm的演算法。。。可惜oi裡面創造的很多方法還沒有or不會被學術界認可價值。。。

竟然沒有說Spielman-Teng方法的嗎。。用來解laplacian system，它的應用帶來了無數關於圖上的問題的更低時間複雜度的近似演算法。雖然是中國人和外國人一起創立的，但這個成果獲得了理論計算機科學領域最高獎哥德爾獎，是哥德爾獎唯一有華人命名的方法，作者滕尚華也是唯一獲得過哥德爾獎的華人。

滕尚華總共獲得過兩次哥德爾獎，另一次獲獎的成果是平滑分析，在理論計算機領域的華人獲獎上僅次於圖靈獎得主姚期智，或者說是中國大陸培養的第一人（Yao是在台灣接受的教育，Teng則是上海交大本科畢業的）。

張友正演算法。就是用黑白棋盤來估算攝像頭的內參矩陣的方法。計算機視覺裡面用的很多。文章的引用亮很大，張友正本人也擔任過某一屆視覺頂會的主席。忘了張是中國人還是華人，不過對回答此題應該沒什麼區別。

zkw線段樹，他的著名的ppt「統計的力量」裡面有，是一種常數極小的線段樹優化

不知道算不算。

主席樹？雖然聽說是引進？

指鹿為馬演算法

(應該是中國人搞出來的吧？)

更相減損。