主頁 >  其他 > 一些動態幾何問題的流式演算法

一些動態幾何問題的流式演算法

2023-06-08 08:16:52 其他

本文為 STOC'04 Algorithms for Dynamic Geometric Problems over Data Streams 的閱讀筆記，

論文作者 Piotr Indyk， 研究領域：高維幾何問題, 流式演算法，摘要資料結構維護, 稀疏傅立葉變換，

1 近似演算法

在假設 \(\text{P}\neq\text{NP}\) 的情況下，近似演算法一般針對 NP 最優化問題(NPO)，有兩點要求

  • 演算法 \(M\) 是確定性或者隨機的多項式演算法，

  • 演算法近似界限 \(r\) 要盡可能低，

    \[r(n)=\sup_{x\in X,|x|=n}\left\{\max\left\{\frac{M(x)}{M'(x)},\frac{M'(x)}{M(x)}\right\}\right\} \]

    其中 \(M'\) 為最優解演算法，\(X\in\text{NPO}\)，

通過 \(r(n)\) 可以定義一系列近似復雜度類，例如 \(f(n)\text{-APX}\) 表示存在近似演算法 \(M\) 使得 \(r(n)\in O(f(n))\) 的問題集合，

一般來說 \(O(1)\text{-APX}\)(可以簡寫為 \(\text{APX}\)) 演算法比較常見，

  • \(\texttt{MAX-3SAT}\) 問題有一個 \(r=\frac{8}{7}\) 的演算法，并且在 Some Optimal Inapproximability Results(1999) 這篇論文中指出，如果存在 \(\epsilon>0\)，\(r=\frac{8}{7}-\epsilon\) 的多項式演算法，則 \(\text{P}=\text{NP}\)，

還有一些問題問題，存在演算法可以無限逼近最優解，但是越逼近時空開銷越大，所以有 \(\text{PTAS}\subset \text{APX}\)，若對于任意 \(\epsilon>0\), \(\exists\) 時間復雜度為 \(O(f(n,1/\epsilon))\) 的演算法，\(f\) 是 \(n\) 的多項式，\(r<1+\epsilon\)，若 \(f\) 為 \(n\) 和 \(1/\epsilon\) 的二元多項式，則為 \(\text{FPTAS}\)，

有時候，若得到的概率分布滿足為

\[P\left(\frac{|M(x)-M'(x)|}{M'(x)}>\epsilon\right)\le \delta \]

近似演算法的演算法復雜度可能涉及三個引數 \(n\), \(1/\epsilon\), \(1/\delta\)，

一般來說常見的近似演算法是貪心等基本的組合演算法，另一類常見的演算法是規約到線性規劃然后采用隨機擾動(rounding)，原始對偶，線性松弛等，

另一類研究的比較少的近似演算法，是針對 \(\sharp P\) 計數問題，常用的方法是馬爾可夫鏈蒙特卡洛方法，

2 流式演算法

流式演算法適用的問題一般比 \(\text{NPO}\) 簡單，大多數是 \(\text{PO}\) 內，但是空間不足以存下之前的輸入或者要求強制在線，需要維護一個摘要或者采樣的演算法，所以很難得到精確解，同樣需要借用用近似演算法的評價標準，

早期流式演算法研 究為一些簡單的統計量的維護：

  1. 中位數. 普遍情況是求第 \(k\) 小，
    流式演算法最早研究 Selection and sorting with limited storage（1978），

    文中介紹了一個隨機資料下空間復雜度為 \(\theta(n ^{1/2})\) 錯誤率極低的流式隨機演算法，
    文章還嚴格證明了 \(p\) 次重復讀入的確定性演算法空間復雜度上下界 \(\Omega(n^{1/p})\) 和 \(O(n^{1/p}\log^{2-2/p} n)\)，

  2. 不同元素個數 \(F_0\)，普遍地有 k 階頻率矩 \(F_k=\sum\limits_x f(x)^k\).
    The space complexity of approximating the frequency moments(1996)

    文章證明了 \(F_0, F_1, F_2\) 存在 \(O(\log n)\) 空間的逼近演算法，用通信復雜度證明了 \(F_k(k\ge 6)\) 則需要 \(n^{\Omega(1)}\) 的空間，
    文章用到了均勻采樣，隨機變數，切比雪夫不等式，切爾諾夫界等概率論工具，以及通信復雜度，將流式隨機演算法的研究形式化，并且將這些工具廣開來成為現在的主流研究方法，可以算這個領域的開山之作，
    文章構造了 \(2\log(1/\delta)\) 個隨機變數 \(Y_i\)，\(E(F_k)=E(\overline{Y_i})\)，然后 \(Y_i=\overline{X_{ij}}\) 為 \(8kn^{1-1/k}/\epsilon^2\) 個隨機變數的均值，\(X\) 為互相獨立的均勻采樣集生成的隨機變數，方法為 \(X=m(r^k-(r-1)^k)\), \(r=|\{q|q\ge p,a_p=a_p\}|\)，其中 \(p\) 為隨機抽樣的下標，維護這樣的 \(X\) 和 \(Y\) 空間復雜度為 \(O\left(\frac{k\log(1/\delta)}{\epsilon^2}n^{1-1/k}(\log n+\log m)\right)\)，
    文中用切比雪夫不等式證明了單個 \(Y_i\) 相對誤差大于 \(\epsilon\) 的概率小于 \(\frac{1}{8}\)，根據切爾諾夫界，可以的到 \(2\log(1/\delta)\) 個 \(Y_i\) 的平均值的越界概率小于 \(\delta\)，文章針對 \(F_2\) 設計了專門的隨機變數，得到了更優的結果，

    隨機變數估計的一個另一個更早的例子是，Probabilistic counting(FOCS,1983) 中提出演算法，\(E(\log F_0)=E(\max(\text{lowbit}(\text{hash}(x))))\)，將統計量 \(F_0\) 用 \(\max(\text{lowbit}(\text{hash}(x)))\) 進行無偏估計，然后用一些概率論的技巧計算出其錯誤率，然后用 Median trick 可以降低錯誤率，

在后續的研究中有人引入和穩態分布和隨機投影，

2.1 采樣

采樣最早是從統計學和資料科學中發展來的方法，看起來很簡單，但是合理的采樣方法可以在流式演算法中起到出乎意料的作用，

  • 用蒙特卡羅方法計算復雜函式的積分或期望，利用均勻分布或其他簡單分布生成隨機變數，然后用樣本均值近似真實值，
  • 用接受-拒絕抽樣或重要性抽樣方法生成難以直接采樣的分布的樣本，利用一個容易采樣的分布作為提議分布，然后根據一定的準則接受或拒絕樣本，或者給樣本賦予不同的權重，
  • 用馬爾可夫鏈蒙特卡羅方法生成難以直接采樣的分布的樣本，利用一個馬爾可夫鏈逐步逼近目標分布的穩態分布，然后從穩態分布中采樣，

2.2 隨機投影

隨機投影是高維問題中經常使用的方法，The Johnson-Lindenstrauss 引理指出高維空間中的一小部分點可以以點之間的距離幾乎被保留的方式嵌入到低維空間中，

通常的方法是把一些高維的范數分解成多個一維和二維的穩態分布來近似，

3 流式問題復雜度上下界證明

3.1 通信復雜度

通信復雜度研究的是，將一個問題的輸入劃分到兩個或多個圖靈機，假設所有圖靈機有無窮的計算能力且彼此互信，協議相同，求解決問題需要傳輸的最小位元量與輸入規模之間的關系，

一個經典的協議是，兩臺圖靈機可以在傳遞 \(O(\log n)\) 個位元的情況下，計算出輸入的中位數，

通信復雜度在很多領域例如計算復雜性理論，量子淺層析
的采樣復雜度下界，電路復雜度下界等領域有重要的作用，

在資料結構空間下界和流式演算法空間下界中的應用方法一般是

一種方法是將流式問題轉化為分布式問題，即將資料流分配給多個參與者，讓他們各自處理自己的資料，并且在必要時進行通信，最后輸出結果，這樣，流式問題的記憶體空間限制就變成了分布式問題的通信限制，
另一種方法是使用資訊論的工具，即將資料流看作是隨機變數，利用熵、互資訊等概念來量化流式問題中所需的資訊量，從而得到通信復雜度的下界，

3.2 可壓縮性分析

可壓縮性分析的核心思想是將流式演算法與有限狀態自動機(DFA) 建立關系，利用 Myhill–Nerode 定理來尋找輸入的等價類數目，確定 DFA 可壓縮的下界從而刻畫出流式演算法空間復雜度的下界，

Stanford University CS154 的 Note 中使用這種方法重新將頻率矩 \(F_k\) 下界復雜度的結論證明了一遍，

3.3 規約

規約是在計算復雜性理論和精細復雜度領域常用的非常技巧，

4 動態幾何問題

4.1 離散高維度量空間

本文研究的問題是在離散 \(d\) 維度量空間 \(D=\{1\cdots\Delta\}^d\) 中動態加點或刪點，維護點集的一個函式，其中中點之間的距離被定義為閔可夫斯基范數 \(d(x,y)=\left(\sum\limits_{i=1}^d|x_i-y_i|^p\right)^{1/p}\)，其中 \(\Delta\) 表示不同元素的個數，

這類問題首先在論文 The Geometry of Graphs and Some of its Algorithmic Applications(1994) 中被探討，文章提出了一些高效演算法，在低維度量空間中以很小的失真嵌入圖，將一些圖上難解的問題例如直徑，最小割問題轉化為幾何問題，使用更高效的近似演算法來解決，

Probabilistic approximation of metric spaces and its algorithmic applications(1996) ，這篇文章提出了任何度量空間都可以分層良分樹(HST)以 polylog 失真概率近似，

在 Approximating a finite metric by a small number of tree metrics(1998)，這篇文章中使用了線性規劃這種確定性演算法構造了大小為 \(O(n\log n )\) 的 HST，使得每條邊期望失真不超過 \(O(\log n \log \log n)\)，

本文同樣使用了 HST，介紹了幾個高維度量空間問題的流式演算法，

4.2 最小生成樹問題

Approximating the minimum spanning tree weight in sublinear time(2001) 文中給出了圖上最小生成樹的亞線性任意近似演算法，時間復雜度為 \(O(\frac{dw}{\epsilon^2}\log\frac{d}{\epsilon})\)，接近下界 \(\Omega(\frac{dw}{\epsilon^2})\)，其中 \(d\) 為點的平均度數，\(w\) 為邊權集合的大小，

The sensor spectrum: technology, trends, and requirements(SIGMOD, 2003) 中對傳感器網路通信代價的研究揭示了高維幾何中最小生成樹問題的實用意義亞線性任意近似演算法，時間復雜度為 \(O(\mathrm{polylog}(n/\epsilon^{O(1)}))\).

同年 Estimating the Weight of Metric Minimum Spanning Trees in Sublinear-Time(2003) 文中的到了高維幾何(度量空間)中中最小生成樹問題的

基于前面文章的作業，在 Estimating the weight of euclidean minimum spanning trees in data streams(2004) 中提出了只支持插入情況下，最小生成樹問題的任意逼近流式演算法，

本文對這個問題得到了在同時支持插入和洗掉操作的情況下以 \(r=O(d\log \Delta)\) 逼近，空間為 \(O(d\log^2\Delta)\) 的流式演算法，

Chen, Jayaram, Levi, Waingarten 將這個問題改進到 \(r\le 1.10\)，空間為 \(\Omega(\sqrt{n})\)，

4.3 匹配問題

空間中匹配問題分為兩種

  • 無色匹配(Minimum Weight Matching)
  • 雙色匹配(Minimum Bi-chromatic Matching)

本文作者指出 Similarity estimation techniques from rounding(1996) 這篇文章的方法足以解決雙色匹配問題，

本文給出了無色匹配的 \(r=O(d\log \Delta)\)，空間為 \(O(d\log^2\Delta\log\log\Delta)\) 的演算法，

文中提到，經過仔細分析，可以做到 \(r=1+\epsilon\)，且空間復雜度只乘上 \(O(1/\epsilon^2)\) 因子的演算法，但是沒有在本文列出，

4.4 工廠選址問題

這類問題由在鐵路上的傳感器通信問題發展而來，

本文給出了一個 \(r=O(d\log^2\Delta)\)，空間為 \(O(d^2\log^2\Delta)\) 的演算法，

在 Streaming Facility Location in High Dimension via New Geometric Hashing(2022) 中，提出了一種基于重要性采樣的演算法，改進到了雙次掃描 \(r=O(1)\)，空間為 \((d\log \Delta)^{O(1)}\)，單次掃描 \(r=O(d/\log d)\)，同時這篇文章給出了一種空間為 \(O(n^{1/\epsilon})\) 的任意近似演算法，

4.5 k-聚類問題

k-聚類問題是幾何問題中非常經典的 NPO 問題，在機器學習等眾多領域有著很重要的作用，已經有眾多有效的啟發式演算法和近似演算法，

在作者所在的時間，已經提出了 \(r=3+\epsilon\)，時間為 \(O(n^{1/2\epsilon})\) 的非流式演算法，目前最優的逼近比是 \(r=2.406\)，由 Improved approximations for Euclidean k-means and k-median, via nested quasi-independent sets(2022) 文中提出，

本文使用了多種工具和演算法例如互斥計數，中點成本估計，本地搜索，貪心等，分別做到了不同的復雜度，

在 The Power of Uniform Sampling for k-Median(2023) 中，作者分析了樸素的均勻采樣的方法，如果要達到 \(r=O(1)\)，則采樣率至少為 \(\Omega(1/\beta)\)，\(\beta\) 為均勻度，如果要達到任意近似，則至少達到 \(O(\mathrm{poly}(k/\epsilon\beta))\) 采樣率，

5 科技

5.1 嵌入分層良分樹(HST)

如果一個有根樹 \(T\) 是 k-HST，則滿足

  • 每個節點到所有子節點的距離相等
  • 從根到葉子節點的路徑上，邊權至少以 \(k>1\) 的比例持續減少，

一個 HST 上的度量空間可以定義為其上所有葉節點，而度量為葉節點之間的最短路，

本文參考了前人的結論，任意 \(\{1\cdots\Delta\}^d\) 的子集 \(P\) 上的度量可以被嵌入一系列 2-HST 度量的概率組合，且失真率小于 \(O(d\log\Delta)\)，

文中以該隨機演算法構建 2-HST

首先對 \(P\) 中所有點增加一個隨機偏移 \(\Delta p\in [0,\Delta]^d\)
樹分為 \(\log\Delta +2\) 層 \(G_0,\cdots, G_{\log\Delta+1}\)，

  • \(G_0\) 為 \(P\) 中的點為葉節點，\(G_{\Delta +1}\) 表示根節點，
  • \(G_i\) 表示包含了 \(P\) 中點的大小為 \(2^{i-1}\) 的網格，
  • \(G_i\) 與 \(G_{i+1}\) 之間按包含關系連邊，邊權為 \(2^i\)，

5.2 規約到高維向量統計問題

這是本文創新提出的方法，令統計量 \(\pi_S(c)\) 表示點集 \(S\) 落在網格 \(c\) 中的數量，這種統計量前人已經研究的很多了，本文用這個統計量的組合來逼近要求的問題，將近似最優化問題轉化為 \(\log\Delta\) 個近似計數問題，

  • 最小雙色匹配近似為 \(\sum\limits_{i=1}^{\log\Delta}2^i\left(\sum\limits_{c\in G_i}|\pi_R(c)-\pi_B(c)|\right)\)，其中 R, B 為兩種顏色的點集，
  • 最小生成樹近似為 \(\sum\limits_{i=1}^{\log\Delta}2^i\left(\sum\limits_{c\in G_i}[\pi_P(c)>0]\right)=\sum\limits_{i=1}^{\log\Delta}2^i|G_i|\)，
  • 最小匹配近似為 \(\sum\limits_{i=1}^{\log\Delta}2^i\left(\sum\limits_{c\in G_i}[\pi_P(c)\equiv 1\pmod 2]\right)\)，
  • 工廠選址問題最小代價近似為 \(\sum\limits_{i=1}^{\log\Delta}\left(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\right)\)，\(f\) 是每個工廠自身的代價，
  • 給定方案的 k-聚類問題的代價近似為 \(\sum\limits_{i=-i_0}^{\log\Delta}(r_{i}-r_{i-1})\left(\sum\limits_{c_i\cap B(Q,r_i)=\emptyset}\pi_P(c_i)\right)\)，其中 \(r_i=(1+\epsilon)^i\)，\(c_i\) 的直徑為 \(\epsilon/\sqrt{2}\times(1+\epsilon)^i\)，\(i_0=O(\log(1/\epsilon)/\epsilon)\)，\(B(Q,r)\) 表示 \(Q\) 中所有點為中心，半徑為 \(r\) 的高維球區域，

6 演算法

6.1 MST

由 Lemma7.1 可以把問題轉化為求 \(w(T)\)，通過定義和恒等變換，很容易得到 5.2 中的式子，

考慮統計每個 \(|G_i|\)，發現可以等價為統計不同元素的個數 \(F_0\)，根據前人的結論可以做到 \(O(\log(n+\Delta^d))=O(d\log\Delta)\) 空間，于是總的空間為 \(O(d\log^2\Delta)\)，

6.2 MWM

根據 Lemma7.2 可以把問題轉化為 \(\log\Delta\) 個 Odd Count 問題，

維護長度為 \((\frac{\Delta}{2^i})^d\) 的陣列 \(x_i\)

  • \(\text{Update}(i,c)\) : \(x_i\leftarrow x_i+c,(c\in\{1,-1\})\)
  • \(\text{OddCount}\) : return \(\sum [x_i\equiv 1\pmod 2]\)

文中提出了一種 \(r=O(1)\)，空間復雜度為 \(O(\log\Delta)\) 的演算法，有常數概率出錯，如果將演算法并行運行 \(O(\log\log\Delta)\) 取均值，可以做到超出界限的概率無限減小變為 \(\frac{1}{2\log\Delta}\)，

文章首先構造了一個概率判定演算法

M="On input \(OC,T\)，\(OC\) 是一個流式 Odd Count 問題，\(T\) 是引數

  1. 初始以 \(1/T\) 的等價概率選取 \(x\) 下標的一個子集 \(R\)， \(s\leftarrow 0\)，
  2. \(\text{Update}(i, c)\)，如果 \(c\in R\), \(s\leftarrow 2 -s\)，
  3. \(\text{OddCount}\) : 輸出 \(s\) 是否為 \(1\)，

這個演算法滿足（證明見 Lemma7.3）

  • 如果真實 \(OC>T\) 則以不小于 \(1/3\) 的概率輸出 YES，
  • 如果真實 \(OC<T/10\) 則以不大于 \(1/10\) 的概率輸出 YES，

通過作者本人之前的文章 pseudorandom generators, embeddings and data stream computation(2000) 中給出的方法，可以用偽亂數生成器以 \(O(d\log \Delta)\) 的空間存盤這個隨機集合，

本文后續沒有介紹如何通過判定問題近似演算法推出計數問題的演算法，推測是等比構造了 \(\log \Delta\) 個 \(T\) 將近似比約束在 \(O(1)\) 的范圍內，然后偽亂數可以在不同的并行運算中復用，
總空間復雜度為 \(O(d\log^2\Delta\log\log\Delta)\)，近似度為規約到 HST 的 \(O(d\log\Delta)\)，

6.3 工廠選址

根據 Lemma7.4，工廠選址問題可以以 \(O(d\log^2\Delta)\) 的近似度規約到 \(\log\Delta\) 個 Bounded Count 問題

維護 \((\frac{\Delta}{2^i})^d\) 個點集 \(S_x\)，

  • \(\text{Add}(x,p)\): \(s_x\leftarrow s_x\cup\{p\}\)，
  • \(\text{Delete}(x,p)\): \(s_x\leftarrow s_x/\{p\}\)，
  • \(\text{BoundedCount}\): return \(\sum\limits_{x}\min\{|S_x|,T\}\)，\(T\) 是引數，

文章對 Bounded Count 給出的演算法是用偽亂數生成器構造了一個值域為 \(T\) 的哈希函式 \(h\)，然后從用這個哈希函式從流中等價采樣了 \(1/T\) 種不同的值，一旦任意一個值落入某個集合，則這個集合按滿的答案 \(T\) 算，這樣問題便轉化為了求不同元素 \(F_0\)，這種轉化可以保證失真在 \(O(1)\) 內，證明見 Lemma7.5，

在作者自己之前的論文中指出，生成隨機哈希函式的偽亂數生成器需要消耗 \(O(\log^2 M)\)，在 \(\log\Delta\) 個并行運算中這些可以復用，總空間復雜度為 \(O(d^2\log^2\Delta)\)，

6.4 k-聚類的搜索演算法

根據 Lemma7.6，存在 \(r=(1+\epsilon)\) 的近似演算法，針對給定的中心點求出 k-median 的代價，

區域搜索也稱為爬山法，是一種很常見的啟發式演算法，缺點是容易陷入區域最優解，

本文參考了 Local search heuristics for k-median and facility location problems(2002) 中的結論證明了在 k-median 問題上區域搜索可以做到 \(r=5\)，

再引入計算代價的失真，總體可以做到 \(r=5+\epsilon\)，空間復雜度 \(O(k\cdot\mathrm{polylog}(\Delta))\)，

如果換成全域搜索可以做到 \(r=1+\epsilon\)，

6.5 k-聚類的貪心演算法

貪心法的思路很簡單，初始讓集合為空，每次選擇使得代價減少最多的點，

文中為了降低復雜度，對貪心做了一些優化，

7 證明

Lemma7.1

若 MST 為 \(\mathcal{T}\)，生成的 HST 為 \(T\), \(\frac{w(T)}{w(\mathcal{T})}\le O(d\log\Delta)\)，

因為 HST 的兩點距離不大于原來兩點距離的 \(O(d\log\Delta)\) 倍

\[w(T)\le\sum_{u,v\in\mathcal{T}}d_T(u,v)\le O(D\log\Delta)w(\mathcal{T}) \]

Lemma7.2

HST 上最小匹配等于 \(n+\sum\limits_i^{\log\Delta}2^im_i\)，\(m_i\) 為 \(G_i\) 的 odd count.

考慮 HST 上每個節點到父節點的邊經過的次數，容易發現，如果經過次數大于 \(1\) 次可以將這兩組匹配交叉使得答案更優，所以最多經過一次，且僅當子樹葉子節點數量為奇數時才需要，

Lemma7.3

6.2 中的判定性問題滿足其中提到的概率條件，

本文參考了 Efficient search for approximate nearest neighbor in high dimensional spaces 中的 Lemma2.1 證明方法，表示兩者相似，

Lemma7.4

如果 HST 上工廠選址問題最優代價是 \(C\)， \(Q=\sum\limits_{i=1}^{\log\Delta}\left(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\right)\) 是 \(C\) 的一個 \(O(\log\Delta)\) 近似，滿足

\[C\le Q+f\le C\log\Delta+f \]

首先，構造一個代價為 \(Q+f\) 的方案，在根節點放一個工廠，然后對所有 \(2^i\times\pi_P(c)\ge f\) 的節點放置一個工廠，這樣的代價為 \(C'\)，\(C\le C'<Q+f\)，
對于等式的另一邊，容易知道對于每一層 \(\sum\limits_{c\in G_i}\min\{2^i\times\pi_P(c),f\}\le C\)，所以總共 \(\log\Delta\) 層加起來小于 \(C\log\Delta\)，

Lemma7.5

6.3 中的演算法是 Bounded Count 的 \(O(1)\) 近似演算法，

若 \(K\) 表示有最終統計出的不同元素個數，\(p(k)=1-(1-1/T)^k\) 表示某個集合有 \(k\) 元素且沒有全部被哈希函式篩出的概率，

\[E(K)=\sum_i p(|S_i|) \]

\[\text{Var}(K)=\sum_i p(|S_i|)-p^2(|S_i|)\le E(K) \]

根據切比雪夫不等式

\[P(|K-E(K)|\ge \epsilon E(K))\le \frac{\text{Var}(K)}{\epsilon^2E(x)^2}\le \frac{1}{\epsilon^2} \]

Lemma7.6

設給定 k-中心點 \(Q\)，k-聚類代價為 \(C(Q,P)\)，

設 \(R_i(Q)=|P-B(Q,r_i)|\)，\(R_i(Q)\) 可以用本文提出的 Exclusive Count 演算法以 \(r=(1+\epsilon)\)，\(\delta=\frac{1}{2}\)，空間為 \(\Omega(k)\) 得到近似 \(\hat{R_i}(Q)\)，滿足

\[R_{i+1}(Q)\le \hat{R_i}(Q) \le R_i(Q) \]

文章使用 \(\hat{C}(P,Q)=(r_i-r_{i-1})\hat{R}_i(Q)\) 近似 \(C(P,Q)\)，

\[\begin{align*} C(Q,P)&=\int_0^{+\infty}|P-B(Q,r)|\mathrm{d}r\\ &\le O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}R_{i+1}(Q)(r_{i+2}-r_{i+1})\\ &\le O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}\hat{R}_i(Q)(r_{i}-r_{i-1})\\ &= O(1+\epsilon)\hat{C}(Q,P) \end{align*} \]

\[\begin{align*} C(Q,P)&\ge O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}|P-B(Q,r_i)|(r_{i}-r_{i-1}) \\ &\ge O(1+\epsilon)\sum_{i=-i_0}^{\log\Delta}\hat{R_i}(r_i-r_{i-1})\\ &= O(1+\epsilon)\hat{C}(Q,P) \end{align*} \]

所以 \(\hat{C}(Q,P)\) 是 \(C(Q,P)\) 的一個 \((1+\epsilon)\) 近似，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/554565.html

標籤：其他

上一篇：【acwing】Trie字串統計

下一篇：返回列表

標籤雲
其他(160546) Python(38215) JavaScript(25478) Java(18209) C(15237) 區塊鏈(8270) C＃(7972) AI(7469) 爪哇(7425) MySQL(7235) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5873) 数组(5741) R(5409) Linux(5347) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4585) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2434) ASP.NET(2403) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) .NET技术(1983) 功能(1967) HtmlCss(1952) Web開發(1951) C++(1933) python-3.x(1918) 弹簧靴(1913) xml(1889) PostgreSQL(1879) .NETCore(1863) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 網閘典型架構簡述

    網閘架構一般分為兩種：三主機的三系統架構網閘和雙主機的2+1架構網閘。 三主機架構分別為內端機、外端機和仲裁機。三機無論從軟體和硬體上均各自獨立。首先從硬體上來看，三機都用各自獨立的主板、記憶體及存盤設備。從軟體上來看，三機有各自獨立的作業系統。這樣能達到完全的三機獨立。對于“2+1”系統，“2”分為 ......

    uj5u.com 2020-09-10 02:00:44 more
  • 如何從xshell上傳檔案到centos linux虛擬機里

    如何從xshell上傳檔案到centos linux虛擬機里及：虛擬機CentOs下執行 yum -y install lrzsz命令，出現錯誤：鏡像無法找到軟體包 前言 一、安裝lrzsz步驟 二、上傳檔案 三、遇到的問題及解決方案 總結 前言 提示：其實很簡單，往虛擬機上安裝一個上傳檔案的工具 ......

    uj5u.com 2020-09-10 02:00:47 more
  • 一、SQLMAP入門

    一、SQLMAP入門 1、判斷是否存在注入 sqlmap.py -u 網址/id=1 id=1不可缺少。當注入點后面的引數大于兩個時。需要加雙引號， sqlmap.py -u "網址/id=1&uid=1" 2、判斷文本中的請求是否存在注入 從文本中加載http請求，SQLMAP可以從一個文本檔案中 ......

    uj5u.com 2020-09-10 02:00:50 more
  • Metasploit 簡單使用教程

    metasploit 簡單使用教程 浩先生， 2020-08-28 16:18:25 分類專欄： kail 網路安全 linux 文章標簽： linux資訊安全 編輯 著作權 metasploit 使用教程 前言 一、Metasploit是什么？ 二、準備作業 三、具體步驟 前言 Msfconsole ......

    uj5u.com 2020-09-10 02:00:53 more
  • 游戲逆向之驅動層與用戶層通訊

    驅動層代碼： #pragma once #include <ntifs.h> #define add_code CTL_CODE(FILE_DEVICE_UNKNOWN,0x800,METHOD_BUFFERED,FILE_ANY_ACCESS) /* 更多游戲逆向視頻www.yxfzedu.com ......

    uj5u.com 2020-09-10 02:00:56 more
  • 北斗電力時鐘（北斗授時服務器）讓網路資料更精準

    北斗電力時鐘（北斗授時服務器）讓網路資料更精準 北斗電力時鐘（北斗授時服務器）讓網路資料更精準 京準電子科技官微——ahjzsz 近幾年，資訊技術的得了快速發展，互聯網在逐漸普及，其在人們生活和生產中都得到了廣泛應用，并且取得了不錯的應用效果。計算機網路資訊在電力系統中的應用，一方面使電力系統的運行 ......

    uj5u.com 2020-09-10 02:01:03 more
  • 【CTF】CTFHub 技能樹 彩蛋 writeup

    ?碎碎念 CTFHub：https://www.ctfhub.com/ 筆者入門CTF時時剛開始刷的是bugku的舊平臺，后來才有了CTFHub。 感覺不論是網頁UI設計，還是題目質量，賽事跟蹤，工具軟體都做得很不錯。 而且因為獨到的金幣制度的確讓人有一種想去刷題賺金幣的感覺。 個人還是非常喜歡這個 ......

    uj5u.com 2020-09-10 02:04:05 more
  • 02windows基礎操作

    我學到了一下幾點 Windows系統目錄結構與滲透的作用 常見Windows的服務詳解 Windows埠詳解 常用的Windows注冊表詳解 hacker DOS命令詳解（net user / type /md /rd/ dir /cd /net use copy、批處理 等） 利用dos命令制作 ......

    uj5u.com 2020-09-10 02:04:18 more
  • 03.Linux基礎操作

    我學到了以下幾點 01Linux系統介紹02系統安裝，密碼啊破解03Linux常用命令04LAMP 01LINUX windows： win03 8 12 16 19 配置不繁瑣 Linux：redhat,centos(紅帽社區版)，Ubuntu server,suse unix:金融機構，證券，銀 ......

    uj5u.com 2020-09-10 02:04:30 more
  • 05HTML

    01HTML介紹 02頭部標簽講解03基礎標簽講解04表單標簽講解 HTML前段語言 js1.了解代碼2.根據代碼 懂得挖掘漏洞 （POST注入/XSS漏洞上傳）3.黑帽seo 白帽seo 客戶網站被黑帽植入劫持代碼如何處理4.熟悉html表單 <html><head><title>TDK標題，描述 ......

    uj5u.com 2020-09-10 02:04:36 more
最新发布
  • 一些動態幾何問題的流式演算法

    本文為 STOC'04 Algorithms for Dynamic Geometric Problems over Data Streams 的閱讀筆記。 論文作者 Piotr Indyk， 研究領域：高維幾何問題, 流式演算法，摘要資料結構維護, 稀疏傅立葉變換。 ## 1 近似演算法 在假設 $\ ......

    uj5u.com 2023-06-08 08:16:52 more
  • 【acwing】Trie字串統計

    Trie樹 學習感受 相比于之前學習的kmp匹配演算法，Trie樹的實作還是非常好理解的。（kmp演算法太難了orz） 從直觀的模擬程序來看，trie樹就像一顆樹一樣，從上（根節點）到下（葉節點）有序串聯起來組成一個字串。 每一個額外標記結束的位置表示字串的結束，通過計算標記數即可指導一共有多少該字 ......

    uj5u.com 2023-06-08 08:16:44 more
  • 位元組技術面都過了，薪資都談好了20K*13結果還是被刷了，問HR,原因

    分享下自己的求職小故事。在一家公司軟體測驗技術面試已經過了，然后和最終面試官溝通了下，面試官提出來一個薪資數字，我接受了這個提議并和hr同步了這個數字。再然后被拒了，理由就是期望薪資和職級不匹配。我詢問后有郵件回復我為什么面試官和面試的地區公司hr說了不算。不知道這是不是大家都曾經遇到過的情況，心情... ......

    uj5u.com 2023-06-08 08:15:34 more
  • “古老”編程語言的最新選擇！華為云發布CodeArts IDE for C/C++

    摘要：華為云CodeArts IDE for C/C++正式上線，歡迎體驗。 本文分享自華為云社區《“古老”編程語言的最新選擇！華為云發布CodeArts IDE for C/C++》，作者：華為云頭條 。 C語言是一種“古老”且應用至今的高級編程語言，它是多種流行編程語言的根源。C++進一步擴充和 ......

    uj5u.com 2023-06-08 08:14:18 more
  • jenkins~權限控制

    jenkins上管理的任務比較多，這時需要有一定的權限管控機制，我們選擇了插件`Role-based Authorization Strategy`來做這事，它支持按著專案前綴去控制你的任務，主要思想還是rbac的模式，通過角色系結權限，通過用戶來系結角色。 # 安裝之后 ![](https://i ......

    uj5u.com 2023-06-08 08:13:57 more
  • 回學校做了個分享

    這周四，收到通知說我能不能周日的時候來學校給大一剛結束的學弟學妹們做一個分享，剛開始是有點猶豫的 因為之前從來沒做過相關的分享，而且覺得時間有點緊怕來不及準備，上一次上臺講東西的時候還是轉正答辯那會 ![image](https://img2023.cnblogs.com/blog/2958925/ ......

    uj5u.com 2023-06-08 08:12:23 more
  • ChatGPT玩法(三)：AI玩轉PPT

    在線免費體驗ChatGpt：https://www.topgpt.one；作為許多職場人士的必備工具，PPT制作一直是一個瑣碎而費時的任務。但最近我發現了一個非常有用的工具網站，它可以通過人工智能來制作PPT，這款工具可以輕松制作出漂亮和專業的PPT，讓你在短短的三分鐘內完成制作，效果也是非常出色的... ......

    uj5u.com 2023-06-08 08:11:58 more
  • 一分鐘了解自動化測驗

    目前自動化測驗并不屬于新鮮的事物，或者說自動化測驗的各種方法論已經層出不窮，但是，能夠明白自動化測驗并很好落地實施的團隊還不是非常多，我們接來下用通俗的方式來介紹自動化測驗…… ......

    uj5u.com 2023-06-08 08:11:24 more
  • 什么是測驗金字塔？如何使用測驗金字塔來構建自動化測驗體系？

    測驗金字塔理論推薦單元測驗應該是數量最多，覆寫范圍最大的測驗種類。道理很簡單，單元測驗成本低，運行速度快，在發現問題的時候解決問題也最快。集成測驗數量次之，最后才是昂貴的端到端測驗。由于端到端測驗經過的環節更多，所以通過端到端測驗發現的問題，解決起來用時更多。 ......

    uj5u.com 2023-06-08 08:11:09 more
  • 4年測驗經驗面試要20K，簡單問了一下，連基礎都不會，我也是醉了&#183;

    現在招個合適的人可真難呀，不是這不會就是那不會，沒有一個讓我滿意的··· 公司前段時間缺人，面試了不少的測驗，結果居然沒有一個符合要求的。一開始瞄準的就是中級測驗工程師的水準，也沒指望來技術大牛，提供的薪資在10-20k，面試的人很多，但平均水平很讓人失望。 細看簡歷很多人都是3、4年作業經驗，但面 ......

    uj5u.com 2023-06-08 08:10:45 more

Copyright © 2010-2020 有解無憂