這是我用偽代碼撰寫的函式：
partition(itemList) {
numPackets = calculateNumOfPackets(listSize, packetSize);
indexOfNextItem = 0;
packetQueue = initialize(numPackets);
for (i = 0; < numPackets; i ) {
// Initialized as a fixed-size list
Packet p = createNew(packetSize);
for (j = indexOfNextItem; j < itemList.length; j ) {
// hasRoom() returns false when packet is at capacity
if (p.hasRoom())
// Guaranteed to run in constant time due to predefined capacity
p.add(item[j]);
else {
indexOfNextItem = j; // keep track of next index for inner loop
break;
}
} // end inner
packetQueue.add(p);
} // end outer
return packetQueue;
}
我希望很清楚，這只是進行磁區并回傳包含輸入串列專案的“資料包”磁區佇列。現在我很確定這是在線性時間內運行的，因為對于外回圈的每次迭代，內回圈都沒有完全運行；它只會運行到當前資料包已滿，此時它會保留它停止的索引的快取，然后跳出內部回圈。結果，我懷疑這實際上是在線性時間內運行的。
我是否正確理解這一點？
uj5u.com熱心網友回復：
如果在 中是createNew(packetSize)線性的，在 中packetSize是initialize(numPackets)線性的，并且numPackets所有p.hasRoom()、 和都是 O(1)，那么您的演算法是 O( )（假設是.p.add()itemList[i]packetQueue.add(p)listSizelistSizelen(itemList)
證明的草圖是每個內回圈最多會執行packetSizeO(1) 次操作，而那個內回圈最多會執行，因此操作的ceil(listSize / packetSize)總數最多會運行在每個回圈中完成的操作。(numPackets 1) * packetSize * nn
uj5u.com熱心網友回復：
您的其中一條評論指出：
給定一個專案串列，該演算法應該將一定數量的這些專案添加到資料包（表示為固定大小的串列）并回傳所述資料包的佇列。因此，如果輸入串列有 100 個專案，并且允許的最大資料包容量為 10，那么您將得到一個包含 10 個資料包的佇列，每個資料包有 10 個專案。
如果這是真的，那么，由于每個專案僅包含在 1 個資料包中，因此您的演算法在專案數量上是線性的 ( O(itemList.length)) - 假設將專案放入資料包是恒定時間的。
僅當回圈計數器是獨立的時，計算嵌套回圈才有意義。如果您知道，就像在這種情況下，串列中的每個專案都被訪問一次且僅一次，并且該訪問是恒定時間的，那么您可以自信地宣告此類代碼在專案數量上是線性的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/497595.html