離散化，把無限空間中有限的個體映射到有限的空間中去，以此提高算法的時空效率。
通俗的說，離散化是在不改變數據相對大小的條件下，對數據進行相應的縮小。例如：
原數據：1,999,100000,15；處理後：1,3,4,2；
原數據：{100,200}，{20,50000}，{1,400}；
處理後：{3,4}，{2,6}，{1,5}；
基本介紹
- 中文名：離散化
- 外文名：Discretization
- 作用：提高算法的時空效率
- 對象：無限空間
- 方式：個體映射到有限的空間中
- 套用領域：程式設計
概述,數據的離散化,使用STL算法離散化,舉例解釋,例1,例2,例3,
概述
離散化是程式設計中一個常用的技巧，它可以有效的降低時間複雜度。其基本思想就是在眾多可能的情況中，只考慮需要用的值。離散化可以改進一個低效的算法，甚至實現根本不可能實現的算法。要掌握這個思想，必須從大量的題目中理解此方法的特點。例如，在建造線段樹空間不夠的情況下，可以考慮離散化。
數據的離散化
有些數據本身很大， 自身無法作為數組的下標保存對應的屬性。如果這時只是需要這堆數據的相對屬性， 那么可以對其進行離散化處理。當數據只與它們之間的相對大小有關，而與具體是多少無關時，可以進行離散化。
例如：
91054與52143的逆序對個數相同。
設有4個數：
1234567、123456789、12345678、123456
排序：123456<1234567<12345678<123456789
=>1<2<3<4
那么這4個數可以表示成：2、4、3、1
使用STL算法離散化
思路是：先排序，再刪除重複元素，最後就是索引元素離散化後對應的值。
假定待離散化的序列為a[n]，b[n]是序列a[n]的一個副本，則對應以上三步為：
sort(sub_a,sub_a+n);
int size=unique(sub_a,sub_a+n)-sub_a;//size為離散化後元素個數
for(i=0;i<n;i++)
a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k為b[i]經離散化後對應的值
對於第3步，若離散化後序列為0,1,2,...,size - 1則用lower_bound，從1,2,3,...,size則用upper_bound。其中lower_bound返回第1個不小於b[i]的值的指針，而upper_bound返回第1個大於b[i]的值的指針，當然在這個題中也可以用lower_bound然後再加1得到與upper_bound相同結果，兩者都是針對以排好序列。使用STL離散化大大減少了代碼量且結構相當清晰。
舉例解釋
離散化是程式設計中一個常用的技巧，它可以有效的降低時間和空間複雜度。下面是用來說明如何運用離散化改進一個低效的的算法的三個例子。
例1
給定平面上n個點的坐標，求能夠覆蓋所有這些點的最小矩形面積。其中，矩形可以傾斜放置，邊不必平行於坐標軸。
這裡的傾斜放置很不好處理，因為我們不知道這個矩形最終會傾斜多少度。假設我們知道這個矩形的傾角是α，那么答案就很簡單了：矩形面積最小時四條邊一定都挨著某個點。也就是說，四條邊的斜率已經都知道了的話，只需要讓這些邊從外面不斷逼近這個點集直到碰到了某個點。你不必知道這個具體應該怎么實現，只需要理解這可以通過某種方法計算出來，畢竟重點在下面的過程。
UVA10173
UVA10173這個算法是否是正確的呢？我們不能說它是否正確，因為它根本不可能實現。矩形的傾角是一個實數，它有無數種可能，你永遠不可能枚舉每一種情況。我們說，矩形的傾角是一個“連續的”變數，它是我們無法枚舉這個傾角的根本原因。我們需要一種方法，把這個“連續的”變數變成一個一個的值，變成一個“離散的”變數。這個過程也就是所謂的離散化。
我們可以證明，最小面積的矩形不但要求四條邊上都有一個點，而且還要求至少一條邊上有兩個或兩個以上的點。試想，如果每條邊上都只有一個點，則我們總可以把這個矩形旋轉一點使得這個矩形變“松”，從而有餘地得到更小的矩形。於是我們發現，矩形的某條邊的斜率必然與某兩點的連線相同。如果我們計算出了所有過兩點的直線的傾角，那么α的取值只有可能是這些傾角或它減去90度後的角（直線按“\”方向傾斜時）這么C(n,2)種。我們說，這個“傾角”已經被我們“離散化”了。
例2
對於某些坐標雖然已經是整數（已經是離散的了）但範圍極大的問題，我們也可以用離散化的思想縮小這個規模。
VOJ1056永遠是離散化的經典問題。大意是給定平面上的n個矩形（坐標為整數，矩形與矩形之間可能有重疊的部分），求其覆蓋的總面積。平常的想法就是開一個與二維坐標規模相當的二維Boolean數組模擬矩形的“覆蓋”（把矩形所在的位置填上True）。可惜這個想法在這裡有些問題，因為這個題目中坐標範圍相當大（坐標範圍為-10^8到10^8之間的整數）。但我們發現，矩形的數量n<=100遠遠小於坐標範圍。每個矩形會在橫縱坐標上各“使用”兩個值，100個矩形的坐標也不過用了-10^8到10^8之間的200個值。也就是說，實際有用的值其實只有這么幾個。這些值將作為新的坐標值重新劃分整個平面，省去中間的若干坐標值沒有影響。我們可以將坐標範圍“離散化”到1到200之間的數，於是一個200*200的二維數組就足夠了。實現方法正如本文開頭所說的“排序後處理”。對橫坐標（或縱坐標）進行一次排序並映射為1到2n的整數，同時記錄新坐標的每兩個相鄰坐標之間在離散化前實際的距離是多少。這道題同樣有最佳化的餘地。
VOJ1056
VOJ1056例3
最後簡單講一下計算幾何以外的一個運用實例（實質仍然是坐標的離散）。
