基本算術運算的大O複雜度

對於像乘法，平方根，對數，標量和矩陣乘積等基本算術運算的廣泛算法，Big-O複雜度是多少？基本算術運算的大O複雜度

在Big-O複雜性方面，是否存在更有效的特殊算法，但在實際解決方案中不是非常普遍（例如，未在流行的軟件庫中實現）？

來源

2010-03-05 psihodelia

+1有趣的問題。爲了澄清，大概他的意思是複雜度隨着位數的增加而增加。 – Tronic 2010-03-05 14:10:54

@Tronic：你認爲位？矩陣產品可能會根據矩陣的大小推測... – Skilldrick 2010-03-05 14:15:05

社區Wiki？ – 2010-03-05 14:16:28

參見http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations方陣的

矩陣乘積：

O（N ）（天真的方法）
O（N ^2.81）（Strassen's algorithm ）。

還有一個O（N ^2.38）Coppersmith–Winograd algorithm，但我不認爲這是廣泛的傳播，由於巨大的隱含常數。

大-INT乘法：

樸素：爲O（n 2 ）
快速傅立葉變換的：O（N日誌N日誌log n）的（Schönhage–Strassen algorithm）。

還有一個n log n＆middot; 2 ^{O（log * n）}算法於2008年發佈，但這個新算法太新，不能廣泛應用。

通常，天真的方法對於正常大小的輸入是足夠好的。

來源

2010-03-05 14:15:49 kennytm

有趣的是，O（N ^2.38）比O（N³）多快。 – psihodelia 2010-03-05 14:19:22

不幸的是，答案是「這取決於」。正如維基百科文章中提到的那樣，該算法沒有被廣泛使用，因爲它實際上只會導致運行時間縮短，從而導致不切實際的巨大輸入。 – 2010-03-05 14:39:58

實際上，O（N^2.38）算法根本不算快，因爲速度比算法複雜度要高。 – Pillsy 2010-03-05 14:40:53

算法沒有複雜性。例如，有各種平方根算法，它們將具有不同的複雜性。

來源

2010-03-05 14:11:19 Skilldrick

乘法是兩個位數組之間的算法。複雜度O（n²），如果我沒有錯。 – Tronic 2010-03-05 14:16:41

@Skilldrick：OP在談論最常用的算法，所以在某種意義上這個答案是無關緊要的。 – 2010-03-05 14:17:09

@Moron：我認爲這個問題自我回答以來已經稍作修改。 – Skilldrick 2010-03-05 14:20:11

由於您的輸入大小通常是固定的（即32位或64位），您會將最簡單的操作視爲O（1）。不管輸入的「大小」如何（即int a = 0; int b = Int32.MaxValue），在正常情況下，您的平臺將執行完全相同的乘法運算，平方根運算，對數運算等等。兩個32位整數）。

一旦你開始看矩陣或表示任意精度的數字，但有人已經鏈接了維基百科摘要，它就會變得很有趣，所以我不會深究。

只是不要使用Schönhage–Strassen乘以「正常」的小數字。它會讓我哭泣。僅僅因爲一個算法是O（ñ）並不意味着它是壞的 - 特別是當ñ幾乎總是2 或2 。

來源

2010-03-05 14:20:18

這是32位整數操作的一個非常好的點。 – Skilldrick 2010-03-05 14:24:32

在實踐中，你對簡單的操作是正確的。然而，作爲一個理論家，我想說的是，你仍然可以談論數字中位數的複雜性。同樣的算法方式對於32b可以很好，但是對於64b會變慢，或者當我們最終達到1024b或者什麼時候......再一次，實際上你是對的，但這仍然是一個有趣的問題。 – 2010-03-05 14:46:39

*點頭*，只要您走出固定長度輸入的安全世界，這絕對是一個有趣的問題。 – 2010-03-05 14:57:10

平方根和對數可以以各種方式實現，極大地影響複雜性（由所需精度判斷）。

如果使用查找表（以及某種插值）實現它們，內存需求確實爆炸，因爲需要更高的精度，但複雜性是查找數組中的值並可能應用插值。

更受歡迎的是它們似乎是通過它們的系列定義來實現的。遞歸或迭代語句多輪，直到達到所需的精度。由於需要更高的精度，因此輪數可能會變得非常高，並且計算本身也會受到精度提高的影響。

來源

2010-03-05 14:22:11 Tronic

+1有趣。這是否意味着N成爲精度？ – Skilldrick 2010-03-05 14:43:31

@skilldrick你絕對可以這樣做。有一些算法是以OUTPUT的大小來衡量的，而不是它們的輸入。他們有一個名字，但它是星期五，所以我不能記住它 - ） – 2010-03-05 15:05:30

有傅立葉算法類型，做整數乘法以及（Schonhage-Strassen）

我認爲有一個版本的Strassen的算法，做比正常的整數乘法稍微好一點，但現在我想起來了，那一個結果是一樣直白...

加法和減法是非常多，只是加法和減法。劃分和平方根可能很有趣，但...

另外：請注意，到目前爲止，每個人都談論過INTEGER算術。一旦你開始浮動/雙打，所有的投注都關閉。然後你進入numerical analysis的世界，這是它自己的整個領域...

來源

2010-03-05 14:37:56

看看BigInteger，在任意長度的整數。就輸入大小而言，一切現在都有成本，這是位數（通常爲K的O(log K)位）。我將使用N作爲下面的位數。

例如，加減法現在是O(N)。乘以O(N^2)（天真）或O(n (log n)^(2+epsilon) )與FFT。

其他算法包括「電源」功能，它需要乘以O(N)。（除了現在每個乘法都有成本！）

對於BigDecimals來說還有其他的複雜性，它是任意長度的十進制等價物，除了一些更基本的操作之外，其中一些更有趣的事情特別是如果你想弄清楚你想要多少精度）。你可以看看Java的實現。

來源

2010-03-05 14:44:26 Larry

一個天真的功率函數實現需要O（n）乘法，但聰明的實現是O（log n）：http：///en.wikipedia。org/wiki/Exponentiation_by_squaring – Juliet 2010-03-05 15:08:09

正如我所提到的，'N'是位數。儘管如此，Powering的確爲'O（log K）'。 – Larry 2010-03-05 15:27:34

大數位的分割和平方根並不比乘法複雜得多。對於這兩種操作，簡單的舊牛頓迭代可以以牛頓迭代僅具有乘法的方式進行排列。由於每個步驟中正確數字的數量增加了一倍，因此我們可以將每一步中的計算精度加倍。

來源

2014-04-21 14:26:28 gnasher729

基本算術運算的大O複雜度

回答

相關問題