問題是從一組 M 無符號整數中找到一對整數 (a,b)，其中 ab 是 n 的倍數。給定一個正整數 n，它小于集合 M 的長度 (m)。這是我寫的片段。
我不太確定這個演算法的時間復雜度是 M 的長度和 n 的值。在排除函式中，最壞的情況是 O(m)。然后它在 m 上的 for 回圈內，然后是 O(m^2)。此外，X 初始化與 n 成比例，所以這里是 O(n)。總共：O(m^2) O(n)，忽略其他 O(1)s。這樣對嗎？
另外，我應該把它r = x % n當作 O(1) 嗎？
歡迎對這里的代碼提出任何與編碼相關的建議！！！大謝謝！
//array X is intialized of size n, all -1. Here the code is omitted.
for (int i = 0; i < m; i )
{
if (currentLength > 1)
{
index = rand() % currentLength;
x = setM[index];
exclude(setM, index, ¤tLength);
r = x % n;
if (X[r] == -1)
{
X[r] = x;
}
else
{
printf("The pair: (%i, %i)\n", X[r], x);
break;
}
}
else
{
break;
}
currentLength -= 1;
}
// to exclude an element based on index, then shift all elements behind by 1 slot
void exclude(int* array, int index, int* length_ptr)
{
if (index != *length_ptr - 1)
{
for (int i = index; i < *length_ptr - 1; i )
{
array[i] = array[i 1];
}
}
}
uj5u.com熱心網友回復：
您需要找到兩個數字 x 和 y x%n==y%n。很容易。使用鍵為 的哈希表x %n。從集合中添加連續的數字，直到找到重復的數字。這將是所需的一對。復雜度是 O(M)。
uj5u.com熱心網友回復：
另外，我應該把它
r = x % n當作 O(1) 嗎？
是的，這是 O(1)
我不太確定這個演算法的時間復雜度......總共：O(m^2) O(n)？
嗯，有點，但還有更多。問題是，m和n是不是獨立的。
考慮這種情況n = 2，讓我們m增加。你的公式會給出 O(m^2) 但這是正確的嗎？不能。因為只有 2 個可能的結果% n（即 0 和 1），for (int i = 0; i < m; i )所以在我們匹配之前回圈只能運行 3 次。無論您增加多少m，都不會超過 3 個回圈。在這些回圈中的每一個中，在最壞的情況下，exclude函式可能會移動到m元素附近。一般來說，for (int i = 0; i < m; i )永遠只能做n 1回圈。
所以m being larger than n你寧愿有 O(n*m) O(n)。當保持n不變時，這變成了 O(m)。所以你的演算法對于m.
現在考慮一個常數m和一個大的增加的情況n。在這種情況下，您的公式給出 O(m^2) O(n)。由于m常數 O(m^2) 也是常數，因此您的演算法對于n.
現在，如果你增加兩者 m，n你的公式給出 O(m^2) O(n)。但是由于m和n都增加了，O(m^2) 最終會支配 O(N)，所以我們可以忽略 O(N)。換句話說，您的演算法對于兩者都是 O(M^2) 。
回顧一下：
O(m) for constant n and increasing m
O(n) for constant m and increasing n
O(m^2) for increasing n and increasing m
歡迎對這里的代碼提出任何與編碼相關的建議
好吧，這index = rand() % currentLength;是只是一個壞主意！
您應該始終測驗陣列中的最后一個元素，即 index = currentLength - 1;
為什么？僅僅是因為這將exclude變成 O(1)。事實上，你甚至不需要它！排除將在執行時自動發生currentLength -= 1;
此更改將提高復雜性，例如
O(1) for constant n and increasing m
O(n) for constant m and increasing n
O(m) O(n) for increasing n and increasing m
O(m) O(n) 可以說只是 O(m)（或只是 O(n)），如您所愿。主要的是它是線性的。
除此之外你不需要currentLength. 將主回圈更改為
for (int i = m-1; i >= 0; --i)
并i用作index. 這將您的代碼簡化為：
for (int i = m-1; i >= 0; --i)
{
r = setM[i] % n;
if (X[r] == -1)
{
X[r] = setM[i];
}
else
{
printf("The pair: (%i, %i)\n", X[r], setM[i]);
break;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/324794.html