嵌套 for、while 和 if 陳述句的時間復雜度是否相同？假設a以長度陣列的形式給出n。
for _ in range(len(a)):
for _ in range(len(a)):
do_something
上面的 for 陳述句將是 O(n2)。
i = 0
while i < len(a) * len(a):
do_something
i = 1
乍一看，上面的回圈可以認為是O(n)，但最終我認為它也是O(n2)。
我對嗎？
uj5u.com熱心網友回復：
我對嗎？
是的！
雙回圈：
for _ in range(len(a)):
for _ in range(len(a)):
do_something
時間復雜度為 O(n) * O(n) = O(n2) 因為每個回圈都運行到n.
單回圈：
i = 0
while i < len(a) * len(a):
do_something
i = 1
時間復雜度為 O(n * n) = O(n2)，因為回圈一直運行到i = n * n = n2.
uj5u.com熱心網友回復：
它確實仍然是 O(n^2)。當您查看具有 len(a)*len(a) 迭代的回圈時，這一點尤其明顯。
你“扁平化”了回圈，但沒有改變作業量，因此它只是一個“風格”的改變，對復雜性沒有影響。
uj5u.com熱心網友回復：
我們需要根據構造恕我直言執行的運算元量來確定時間復雜度。概括并說某些回圈具有特定的時間復雜度是不正確的。
嵌套 for 回圈的時間復雜度通常為 O(n 平方) - 并非總是如此。一些涉及的嵌套 for 回圈也可能只有 O(n) 復雜度。單個 if 陳述句通常是 O(1)，因為您只進行基本比較。while 回圈可以是任何東西，具體取決于您的退出條件。
雖然記住這些概括可能很有用，但我們應該始終檢查執行的運算元量以確定復雜性。
uj5u.com熱心網友回復：
讓我補充其他答案。
將兩個嵌套回圈重寫為單個回圈時，時間復雜度會改變嗎？
如果他們做同樣的作業，復雜性不會改變。:-) 如果確實如此，那么（至少）其中一個正在做不必要的作業。
如果走得太遠，我深表歉意，但讓我猜一下：您的想法是：
- 嵌套回圈 --> 乘法，即“n * n”（或“n * m”），其中“n”是“通常”。
- 單回圈 --> 按原樣使用“n”，其中“n”是“通常的”。我猜你在大多數練習中都見過“n”代表“size”。
如果這是你的想法，它只需要一個調整：對于單個回圈，如果 "n" 是回圈的長度，請注意 n = len(a) * len(a); 如果將“n”的含義從一個問題更改為另一個問題，則無法比較（對于嵌套回圈，n = len(a)）。在任何情況下，這兩個代碼都具有 O(len(a) * len(a)) 復雜性，這是您已經發現的。
uj5u.com熱心網友回復：
是的，總的來說，您是對的，盡管有一個小警告值得一提。
在某些情況下，例如訪問磁盤或將頁面交換到記憶體中，它可能會產生影響——在某些情況下會有很大的不同——讀取是否在某種塊內是順序的，訪問不同的塊時會產生開銷。有時，這可能對≥2D 矩陣中的回圈順序非常敏感。
舉個具體的例子，假設我們有 128 位元組的資料頁，我們一次只能保存一個，快取了最新的頁，我們想制作一個 128x128 的陣列并處理每個元素，我們沒有不關心處理的順序，但是交換頁面會產生處理元素的 60 倍延遲，并且該處理需要 1 秒，因此延遲為 60 秒 == 1 分鐘。明白我為什么選擇 x60 了嗎？如果我們談論的是 OG 1x CD-ROM 驅動器、互聯網、很多東西，甚至當你有“快取未命中”時的記憶體，這可能是保守的，盡管它可能沒有那么戲劇化。
我的 C 有點生疏，不要抱怨使用幻數而不是常量，但您通常可以按照以下方式做一些事情：
uchar *buffer;
int x, y;
buffer = malloc(128 * 128);
for(x=0 ; x<128 ; x ) {
for(y=0 ; y<128 ; y ) {
process_thingie(buffer[x*128 y]);
}
}
因此處理需要 128*128 ~= 16k 秒 ~= 4? 小時，并且您一次訪問一個頁面，因此又是 128 分鐘，總共需要 6? 小時。
相反，您可以完全忽略 2D 方面 - 如您的問題所示：
for(i=0 ; i<128*128; i )
process_thingie(buffer[i]);
這給出了相同的結果，16k 條記錄，每頁交換一次，你就沒有問題：
“你是對的。”
但。假設無論出于何種原因，您都會反轉內部/外部回圈：
for(y=0 ; y<128 ; y ) {
for(x=0 ; x<128 ; x ) {
process_thingie(buffer[x*128 y]);
}
}
（或只是更改x*128 y為y*128 x，同樣的事情）
嗯，這是非常不同的。每次后續訪問與前一次訪問相比，步長為 128 位元組，因此我們有義務在每次迭代時交換新頁面
That takes 128*128 ~= 16k seconds ~= 4? hours for the processing, but with a swap every time, that's ALSO 16k minutes, for a total of about 11? DAYS
technically it's still O(n2)... there's just another n hiding. Either implementation will scale at O(n2) relative to itself
CD-ROM game developers, for example, had to concern themselves with the physical placement of file on the disk (not quite the same but see this discussion of related issues in Myst),
Nowadays this is rarely such a concern, SSDs are crazy fast, and optimizing compilers (I think?) are usually smart enough to see what's up and swap the two loops (yeah), but they certainly can not catch everything, there may be some good reason you need to access the data in this order, you might need optimum performance for a certain task.
This does still come up in real life, programmers do sometimes need to be aware of it - I think this is one of the things game console developers still need to obsess over.
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/438487.html
上一篇：獲取具有時間范圍的時間間隔
下一篇：有條件的函式陣列