我試圖在 A 中找到一對 (x,y) 使得 xy = 0 (mod n)
下面是我寫的腳本。
如果 n 是常數，運行時間復雜度是多少？--> 所以，這被問到了，但不是一直不變嗎？我有點困惑，問題是“輸入是一個正整數 n ...”
def find_equal_pair_mod_n(n, A):
assert len(A) > n
X = [-1] * n
print(X)
for i in range(len(A)-1,-1,-1) : #loop backwards
print(i)
a = A[i]
print(a)
print(len(A))
A.pop(i)
r = a % n
if X[r] == -1:
X[r] = a
else:
return(X[r], a)
uj5u.com熱心網友回復：
簡短的回答
- “就
n和而言，運行時復雜度是m多少？”。正確答案是O(n)。 - “如果
n是常數，運行時間復雜度是多少？”。正確答案是O(1)。
解釋
- 當你迭代你的回圈時，你只能做
n 1迭代，因為n除以 時只有不同的余數n。因此，您肯定會在n 1或更少的迭代中找到答案。 - 如果
n是恒定的，您仍然需要n 1或更少的迭代來找到答案，因此您需要恒定的時間來解決您的問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/420538.html
標籤：
上一篇：如何自動將具有許多連接的類似SQL的查詢分解為離散的、獨立的步驟？
下一篇：計算二維圖中偶數/奇數的總數