時間分析矩陣的嵌套循環的複雜性

假設我有一個具有X行和Y列的矩陣。元素的總數是X * Y，是否正確？那麼這是否使得n = X * Y？時間分析矩陣的嵌套循環的複雜性

for (i=0; i<X; i++) 
{ 
    for (j=0; j<Y; j++) 
    { 
     print(matrix[i][j]); 
    } 
}

那麼這是不是說這個嵌套for循環是O（n）？或者我誤解了時間複雜性的工作原理？我認爲所有嵌套for循環都是O（n^2），但是如果它通過X * Y調用print（），這並不意味着時間複雜度是O（X * Y）而X * Y等於n？

來源

2012-04-27 vgmoose

-2

這個答案是匆匆寫成，並收到了一些downvotes，所以我決定了澄清，並把它改寫

算法的時間複雜度是在尺寸方面的算法的操作次數的表達該算法打算解決的問題。

這裏涉及兩種尺寸。

的第一尺寸是矩陣X×Y的元素的數量。這對應於什麼是在複雜性理論爲尺寸輸入的公知的。令k = X×Y表示矩陣中元素的數量。由於孿生循環中的操作數是X×Y，所以它在O（k）中。
第二大小是矩陣的列數和行數。令m = max（X，Y）。孿生循環中的操作數量爲O（m^2）。通常在線性代數中，這種大小用於表徵矩陣在m×m矩陣上運算的複雜性。

當您談論複雜性時，您必須精確指定如何對實例問題進行編碼以及使用哪個參數指定其大小。在複雜性理論我們通常假設輸入的算法給出一些有限字母表來一串字符和衡量問題的一個實例的算法在操作的數量上限方面的複雜性由長度爲n的字符串給出。即在複雜性理論中，n通常是輸入的大小。

在實際中複雜性分析算法我們經常使用其他度量的大小的實例在特定的上下文中更有意義。例如，如果A是一個曲線圖的連接矩陣，我們可以使用頂點V的數量作爲問題的一個實例的複雜性的度量，或如果A是作用於一個向量空間，我們可以線性算子的矩陣使用向量空間的維度作爲這樣的度量。對於正方形矩陣，約定是用矩陣的維度來指定複雜度，即用n來度量作用在n×n矩陣上的算法的複雜度。即使它可能與複雜性理論的慣例相矛盾，它通常具有實際意義並且也符合具體應用領域的慣例。

讓我們把名字矩陣掃描我們的雙循環。您可以合法地說，如果矩陣掃描的實例的大小是矩陣的字符串編碼的長度。假設有限大小的條目，它是矩陣中元素的個數，k。那麼我們可以說的複雜度矩陣掃描在O（k）中。在另一方面，如果我們取M = MAX（X，Y）作爲表徵一個實例的複雜度的參數，因爲在許多應用中習慣，則複雜性矩陣掃描用於X×Y矩陣意願也O（平方公尺）。對於方形矩陣X = Y = m和O（k）= O（m^2）。

注意：有些人在評論中問道，我們是否總能找到問題的編碼，以減少任何多項式問題線性問題。這不是真的。對於某些算法，操作次數的增長速度比其輸入的字符串編碼的長度更快。例如，沒有算法將兩個m×m矩陣與θ（m^2）個操作數相乘。這裏輸入的大小增長爲m^2，但是Ran Raz證明了操作的數量增長至少與m^2log m一樣快。如果n在O（m^2）內，那麼m^2 log m在O（n log n）中，並且最好的已知算法複雜度隨着O（m ^（2 + c））= O（n ^（1+ c/2）），其中對於普通迭代算法，c對於Coppersmith-Winograd算法的版本至少爲0.372，c = 1。

來源

2012-04-27 04:56:44

你怎麼扣除''O（平方公尺）= O（N）''？這顯然是錯誤的！它是如何工作的，我們只是把每個多項式問題都放在線性空間中:) – user221931 2014-03-04 03:34:08

你說：'一般讓m = max（X，Y），那麼O（m^2）= O（n）''。無論你如何撫摸它，這都是公然錯誤的。但是''O（X * Y）= O（n^2）''是完全有效的，你不需要''n = max（X，Y）''因爲它很大O不是大的Theta符號和它是隱含的。現在你有了答案的方式，你聲稱「嵌套循環是O（n）」，如果你製作一份文件並證明它是用於諾貝爾的話。 – user221931 2014-03-04 15:42:22

爲了澄清OP和其他人， 'O（X * Y）''是''O（n^2）''，因爲X和Y是變量。如果X OR Y是一個常量（不管多大），O（X * Y）''可以是'O（n）''，因爲它不會增長。最後，如果X和Y是常量，「O（X * Y）」可以是「O（1）」，那麼該函數不能增長，並且執行時間相同。 – user221931 2014-03-04 15:52:25

如果你有一個大小爲rows *列的矩陣，那麼內部循環（比方說）是O（列），嵌套循環一起是O（行*列）。

對於N^2的問題大小，您正在混淆N的問題大小。你可以說你的矩陣是N的大小，或者你的矩陣的大小是N^2，但是除非你的矩陣是正方形，否則你應該說你有一個大小爲行*矩陣的矩陣。

來源

2012-04-27 04:48:36 ninjagecko

你說得對，當你說n = X x Y但你說錯了，當你說嵌套循環應該是O(n)。如果你幹運行你的代碼，可以理解嵌套循環的含義。您會注意到，對於外部循環的每次迭代，內部循環運行n（或者什麼是尺寸條件）次。因此，通過簡單的數學，你可以推斷出它的O(n^2)。但是，如果你有，當你將遍歷(X x Y)（例如，只有一個循環：for(i = 0; i<(X*Y); i++)元素，那麼這將是O(n)，因爲你不會在任何時間點重新啓動迭代希望這是有道理

來源

2012-04-27 04:49:09 noMAD

。
一般情況下，我以爲所有嵌套的for循環是爲O（n^2），

你是錯了。什麼混淆你我的猜測是，人們往往作爲一個例子廣場（X == Y）矩陣使用所以複雜度是n * n（X == n，Y == n）

如果你想要t o練習你的O（*）技能試圖找出爲什麼矩陣乘法是O（n^3）。如果你不知道矩陣乘法的算法，很容易在網上找到它。

來源

2012-04-27 04:54:11 NoSenseEtAl

時間分析矩陣的嵌套循環的複雜性

回答

相關問題