減少給定程序的空間複雜度或時間複雜度會更好嗎？

Question

網格照明：給定一個NxN網格和一系列燈座標。每個燈爲其x軸上的每個方形，y軸上的每個方形以及位於其對角線上的每個方形提供照明（想象一下國際象棋中的女王）。給定一組查詢座標，確定該點是否被照亮。當檢查所有與該查詢相鄰或相關的燈時，該查詢就會被關閉。用於變量/陣列的範圍分別爲大約：10^3 <Ñ< 10^9,10^3個<燈< 10^9,10^3 <查詢< 10^9

好像我可以得到一個，但不是兩個。我試圖把它降低到對數時間，但我似乎無法找到解決方案。我可以減少空間的複雜性，但事實並非如此快速，指數級。我應該在哪裏關注速度或空間？另外，如果您對如何解決此問題有任何意見，請發表評論。

Answer 1

對於一輛汽車來說，快一點還是長途駕駛一點燃料會更好嗎？這取決於具體情況。

這是一個建議。

首先，請注意，您可以使用第一個點作爲nw-se和ne-sw的「原點」來輸入所有對角線的輸入。通過這一點的對角線都編號爲零。例如在東北方向上，每個像素的n-se對角線增加，並且向西南方向減小（負）。類似地，ne-sw在例如數字上增加。西北方向，向東南方向減小（負向）。

給定起點，很容易寫出從（x，y）座標到相應對角線數的恆定時間函數。

現在每組燈座標自然與4個數字相關聯：(x, y, nw-se diag #, sw-ne dag #)。你不需要明確地存儲這些。而要4個地圖xMap，yMap，nwSeMap和swNeMap使得，例如，XMAP [X]生產的所有燈的列表中與座標x座標x，nwSeMap [nwSeDiagonalNumber（X，Y）]產生所有的列表該對角線上的燈和其他地圖上的燈相似。

給定查詢點，查找它對應的4個列表。從這些很容易處理相鄰的廣場。如果任何列表大於3，則刪除相鄰的正方形不能使其變爲空，因此查詢點會亮起。如果它只有3個或更少，那麼查看它們是否相鄰是一個持續時間操作。

該解決方案要求輸入點以4個列表表示。由於它們需要在一個列表中表示，因此您可以爭辯說，該算法只需要一個與輸入相關的恆定空間因子。 （即與mergesort相同的成本）

對於4個散列表查找，運行時間預計爲每查詢點不變。

沒有太大的麻煩，這個算法可以拆分，所以如果燈柱的數量很大，它可以減少映射。

但是，在一臺大型機器上運行它可能已經足夠和容易了。有十億個lamposts和仔細的數據結構選擇，使用像C這樣的非盒裝結構語言來實現每個移位寄存器24個字節並不難。所以一個〜32Gb的RAM機器應該工作得很好。使用多個線程構建地圖需要一些同步，但這隻能完成一次。查詢可以是隻讀的：不需要同步。一臺不錯的10核心機器應該在一分鐘內完成十億次查詢。