假設(shè)列表房由0(= x)的對(duì)(x，pop)組成， 4 * L的位置和流行的人口。

我們想要最大化的目標(biāo)函數(shù)是

def revenue(i):

return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

樸素算法O(LN)算法簡(jiǎn)單：

max_revenue = max(revenue(i) for i in range(4*L))

但是，完全重新評(píng)估每個(gè)地點(diǎn)的收入是非常浪費(fèi)的。

為了避免這種情況，請(qǐng)注意這是一個(gè)分段線性函數(shù);所以它的導(dǎo)數(shù)是分段常數(shù)，不等式在兩點(diǎn)上：

>在房子我，衍生物從斜坡變化到2 *人口[i]

>在島上對(duì)面的位置，衍生物從斜坡變化到斜坡 – 2 *人口[i]

這使事情很簡(jiǎn)單：

>我們只需要檢查實(shí)際的房屋或?qū)γ娴姆孔?#xff0c;所以復(fù)雜度下降到O(N2)。

>我們知道如何更新房屋i-1到房屋i的坡度，只需要O(1)個(gè)時(shí)間。

>由于我們知道位置0的收入和斜率，并且由于我們知道如何迭代地更新斜率，所以復(fù)雜性實(shí)際上下降到O(N)：在兩個(gè)連續(xù)房屋/對(duì)立房屋之間，我們可以將通過(guò)距離斜率獲得收入差額。

所以完整的算法是：

def algorithm(houses, L):

def revenue(i):

return sum(pop * min((i-j)%(4*L), 4*L - (i-j)%(4*L)) for j,pop in houses)

slope_changes = sorted(

[(x, 2*pop) for x,pop in houses] +

[((x+2*L)%(4*L), -2*pop) for x,pop in houses])

current_x = 0

current_revenue = revenue(0)

current_slope = current_revenue - revenue(4*L-1)

best_revenue = current_revenue

for x, slope_delta in slope_changes:

current_revenue += (x-current_x) * current_slope

current_slope += slope_delta

current_x = x

best_revenue = max(best_revenue, current_revenue)

return best_revenue

為了保持簡(jiǎn)單，我使用sorted()來(lái)合并兩種類型的斜率變化，但這并不是最優(yōu)的，因?yàn)樗哂蠴(N log N)的復(fù)雜性。如果想要更好的效率，可以在O(N)時(shí)間內(nèi)生成對(duì)應(yīng)于對(duì)面房屋的排序列表，并將其與O(N)中的房屋列表合并(例如使用標(biāo)準(zhǔn)庫(kù)的heapq.merge) 。如果要最小化內(nèi)存使用情況，您也可以從迭代器而不是列表流式傳輸。

TLDR：該解決方案實(shí)現(xiàn)了O(N)的最低可行復(fù)雜度。

總結(jié)

以上是生活随笔為你收集整理的python 效率 算法_python – 算法(prob solve)实现最快的运行时间的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。