我有一個不同長度的串列串列，我的演算法在子串列中的每個元素上運行。
我的時間復雜度應該是多少？
我不知道是否可以寫 O(n * m)，因為父串列的 n 長度，m 是 t E 子串列的平均長度，或者可能 O(n)，因為 n 是總元素的數量。
請解釋一下符號的含義（例如 n 是父串列的長度）。
uj5u.com熱心網友回復：
如果您有每個n包含元素的子串列，則表示正在處理的元素總數，因此它的復雜度為.mn*mO(n*m)
如果您的子串列的元素數量不相等，可以將其總結為O(N)，其中N是陣列中的元素總數。
uj5u.com熱心網友回復：
您可以定義變數，因此可以說“O(n) 其中 n 是輸入的大小”。
您的情況似乎類似于“稀疏”矩陣方法：稀疏矩陣具有明確定義的寬度和高度，以及總大小（非零元素）。演算法性能描述可以酌情使用所有三個引數。
歸根結底，應該是關于什么便于描述演算法。
uj5u.com熱心網友回復：
您總共執行了 N 次操作。因此，除非您的演算法訪問其中的一些其他元素，否則它會成為 O(N) 操作。從一個子串列轉換到下一個子串列的行為，即使需要相當長的時間，也是一個 O(m) 操作。但是由于 m 小于 N，您可以忽略它，因為隨著 N 變得非常大，它會壓倒 O(m) 時間。事實上，“順序”分析的全部目的是展示演算法在極端條件下的回應能力。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/475520.html
上一篇：二叉堆能做什么而二叉搜索樹不能？