#90: 時間複雜度 O(M^2*N*log M)


123q (unknown)

School : Not Student
ID : 363
IP address : [114.24.66.197]
Last Login :
2025-03-30 23:40:49
e039. 最接近的子矩陣和 (*) -- 108 高中全國賽AP325 | From: [203.68.187.123] | Post Date : 2024-12-31 18:03

 

  • 外部循環:兩層循環遍歷矩陣的上下邊界,時間複雜度為 O(M^2)。
  • 內部循環:對於每一對top 和bottom,我們遍歷所有列,且每次更新和查找前綴和,時間複雜度為O(N),並且每次查找和插入操作的時間複雜度為O(1) (由於使用unordered_set)
  • 由於 set 裡的運算(插入和尋找)是對數時間複雜度的,所以本演算法的時間複雜度大致是 O(M^2 * N * log M),對於大矩陣會有較高的時間消耗。

 

 
ZeroJudge Forum