為什么使用外部回圈初始化二維矩陣中的對角線比在串列理解中快得多？我正在使用串列推導式，并且在一個涉及動態編程的問題中，我在 Leetcode 中超出了時間限制。我認為我的演算法是錯誤的。切換到外部回圈解決了一半的時間，我的解決方案被接受了。這是我的帶有計時的代碼示例。第一種方法比我機器上的第二種方法慢 6 倍。
#super slow
from time import perf_counter
s=perf_counter()
dpArray=[[ True if i==j else False for j in range(1000)] for i in range(1000) ]
print(f"Initialized in {perf_counter() - s:0.4f} seconds")
#super fast
s=perf_counter()
dpArray=[[False]*1000 for i in range(1000) ]
for i in range(1000):
dpArray[i][i]=True
print(f"Initialized diagonal in {perf_counter() - s:0.4f} seconds")
Execution:
Initialized in 0.0645 seconds
Initialized diagonal in 0.0095 seconds
如果有人對解決方案感興趣，這里是慢版，幾乎沒有通過。我不得不做一些調整以避免 TLE 錯誤：
class Solution:
def longestPalindrome(self, s: str) -> str:
dp = [[ True if i==j else False for j in range(len(s))] for i in range(len(s)) ]
ans=s[0]
for j in range(len(s)):
for i in (range(j)):
if s[i]==s[j] and (dp[i 1][j-1] or j==i 1):
dp[i][j]=True
if j-i 1>len(ans):
ans=s[i:j 1]
return ans
快速版：
class Solution:
def longestPalindrome(self, s: str) -> str:
dp = [[False]*len(s) for _ in range(len(s)) ]
for i in range(len(s)):
dp[i][i]=True
ans=s[0]
for j in range(len(s)):
for i in range(j):
if s[i]==s[j] and (dp[i 1][j-1] or j==i 1):
dp[i][j]=True
if j-i 1>len(ans):
ans=s[i:j 1]
return ans
uj5u.com熱心網友回復：
這兩種方法并不等效。在串列推導式中，您執行 1,000,000 次比較 ( if i==j) 而在第二個中您根本沒有任何比較。
也是[False]*1000一個內置的快捷方式，可能比 for 回圈執行得更快。
請注意，這兩種方法的時間復雜度都是O(n^2)，但這并不意味著一種方法不能比另一種方法快。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/355010.html