b446: 史蒂芙的煩惱
b446: 史蒂芙的煩惱
題 目:
兩 個 人 輪 流 在 一 個 大 棋 盤 上 下 棋，每 一 步 棋 的 得 分 根 據 這 一 步 棋 與 最 鄰 近 的 敵 方 棋 子 的 曼 哈 頓 距 離。
對 於 兩 個 點 $p,q$ 座 標 $(px, py), (qx, qy)$，曼 哈 頓 距 離 為 $\lvert px−qx \rvert +\lvert py−qy \rvert$。
對 於 兩 個 點 $p,q$ 座 標 $(px, py), (qx, qy)$，曼 哈 頓 距 離 為 $\lvert px−qx \rvert +\lvert py−qy \rvert$。
solve:
因 為 想 學 KDT，所 以 就 用 它 來 解 這 題 了。
KDT 是 一 種 樹 狀 資 料 結 構，可 以 用 來 查 詢 近 K 點 的 距 離。
但 是 如 果 K 點 約 等 於 點 的 數 量，效 率 就 變 成 一 般 暴 力 了(可 能 還 比 暴 力 慢
KDT 的 原 理 簡 單 的 說 就 是 用 第 i 維 最 中 間 的 點 當 作 分 割 線，
把 左 邊 的 點 推 進 左 子 樹，右 邊 同 理。
(當 作 基 準 的 維 度 在 遞 迴 進 下 一 層 時 會 + 1，比 如，第 一 層 是 以 $x$ 為 準，那 下 一 層 則 是 $y$，再 下 一 層 為 $z$ ... 以 此 循 環)
把 左 邊 的 點 推 進 左 子 樹，右 邊 同 理。
(當 作 基 準 的 維 度 在 遞 迴 進 下 一 層 時 會 + 1，比 如，第 一 層 是 以 $x$ 為 準，那 下 一 層 則 是 $y$，再 下 一 層 為 $z$ ... 以 此 循 環)
--------效率--------
設 $N$ = 點 集 數 量, $K$ = 維 度 數 量
插 入: $O(log^2 N)$
刪 除: $O(N^{N - \frac{1}{K}})$
查 找: 平 均 $O(log N)$、最 壞 $O(N^{N - \frac{1}{K}})$
-----------------------
code:
留言
張貼留言