布隆过滤器定义长度为m的数组，插入n个元素，k个哈希函数，已知m和n的值，k的值为多少时，求误判率最低的推导过程？

太过爱你忘了你带给我的痛 2022-11-17 14:40 49阅读 0赞

### 布隆过滤器是怎么存储数据的？ ###

这里m=11，数组长度为11，n=3，插入3个元素，分别是hello、how、yes，k=3，使用了3个哈希函数，每插入一个元素要经过三个哈希函数的运算。

①插入hello元素，需要经过3个哈希函数，得出3个不同的哈希值索引【1,3,6】，那么在1,3,6的位置设置为1。

②插入how元素，需要经过3个哈希函数，得出3个不同的哈希索引值【4,8,10】，那么在4,8,10的位置设置为1。

③插入yes元素，需要经过3个哈希函数，得出3个不同的哈希值索引值【0,1,3】，那么在0,1,3的位置设置为1。

④误判的情况：判断ok元素是否存在？ok这个元素经过3个哈希函数运算以后，得出的索引值也是【0,1,3】，这个索引值和yes元素是一样的，然而布隆过滤器认为ok这个元素是存在的，但实际上不存在的，因为哈希值冲突了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70][]

### 设布隆过滤器的长度为m，插入n个素，进行k个哈希函数运算，已知m和n的值，问：当k的值为多少的时候，误判率最低？ ###

解：

长度为m，插入1个元素，1个哈希函数运算的情况下，某一位是1的概率为：![\\frac\{1\}\{m\}][frac_1_m]，那么某一位为0的概率就是 ![1-\\frac\{1\}\{m\}][1-_frac_1_m]

长度为m，插入n个元素，1个哈希函数运算的情况下，一次插入1个元素（每次插入的元素可能有某几次是重复的），插入n次，相当于插入了n个元素，插入这么多次以后，某一位仍然为0的概率是![(1-\\frac\{1\}\{m\})^\{n\}][1-_frac_1_m_n]

长度为m，插入n个元素，每插入一个元素之前就经过k个哈希函数运算的情况下，一次插入1个元素，插入n次，相当于插入了n个元素，插入这么多次以后，某一位仍然为0的概率是![(1-\\frac\{1\}\{m\})^\{kn\}][1-_frac_1_m_kn]

反过来，某一位为1的概率就是![1-(1-\\frac\{1\}\{m\})^\{kn\}][1-_1-_frac_1_m_kn]

那么，某两位同时为1的概率就是![\[1-(1-\\frac\{1\}\{m\})^\{kn\}\]^\{2\}][1-_1-_frac_1_m_kn_2] ，某三位同时为1的概率就是![\[1-(1-\\frac\{1\}\{m\})^\{kn\}\]^\{3\}][1-_1-_frac_1_m_kn_3] ，某k位同时为1的概率就是![\[1-(1-\\frac\{1\}\{m\})^\{kn\}\]^\{k\}][1-_1-_frac_1_m_kn_k]，这个概率，就是误判率，因为检查是否有某个元素的时候，某k位同时为1，说明有这个元素，但这个元素是外来的，本身不存在于集合当中。

误判率 ![f(k) = \[1-(1-\\frac\{1\}\{m\})^\{kn\}\]^\{k\}][f_k_ _ _1-_1-_frac_1_m_kn_k] ，其中m，n都是常数，求这个函数是最小值的时候，k等于多少？

当m足够大的时候，也就是数组足够长的时候，能够确保误判率足够，此时，把式子变形：

![f(k) = \[1 - (1 - \\frac\{1\}\{m\})^\{-m\\cdot \\frac\{-kn\}\{m\}\}\]^\{k\}][f_k_ _ _1 - _1 - _frac_1_m_-m_cdot _frac_-kn_m_k]

因为m是一个很大的数字，可能是100万，1000万这个数量级别的，足以让![(1 - \\frac\{1\}\{m\})^\{-m\}][1 - _frac_1_m_-m]趋近于 e

所以，![f(k) = (1-e^\{-\\frac\{n\}\{m\}\\cdot k\})^\{k\}][f_k_ _ _1-e_-_frac_n_m_cdot k_k]

两边都取ln对数得：

![lnf(k) = ln(1-e^\{-\\frac\{n\}\{m\}\\cdot k\})^\{k\}][lnf_k_ _ ln_1-e_-_frac_n_m_cdot k_k] ，即 ![lnf(k) = k\\cdot ln(1-e^\{-\\frac\{n\}\{m\}\\cdot k\})][lnf_k_ _ k_cdot ln_1-e_-_frac_n_m_cdot k]

令 ![b = e^\{\\frac\{n\}\{m\}\}][b _ e_frac_n_m] ，那么 ![lnf(k) = k\\cdot ln(1-b^\{-k\})^\{k\}][lnf_k_ _ k_cdot ln_1-b_-k_k]

两边求导：

![\\frac\{1\}\{f(k)\}\\cdot \{f'(k)\} = ln(1-b^\{-k\})+k\\cdot \\frac\{1\}\{1-b^\{-k\}\}\\cdot (-b^\{-k\}\\cdot lnb\\cdot (-1))][frac_1_f_k_cdot _f_k_ _ ln_1-b_-k_k_cdot _frac_1_1-b_-k_cdot _-b_-k_cdot lnb_cdot _-1]

![\\frac\{1\}\{f(k)\}\\cdot \{f'(k)\} = ln(1-b^\{-k\})+\\frac\{k\\cdot b^\{-k\}\\cdot lnb\}\{1-b^\{-k\}\}][frac_1_f_k_cdot _f_k_ _ ln_1-b_-k_frac_k_cdot b_-k_cdot lnb_1-b_-k]

因为![f(k) = (1-e^\{-\\frac\{n\}\{m\}\\cdot k\})^\{k\}][f_k_ _ _1-e_-_frac_n_m_cdot k_k]，且![b = e^\{\\frac\{n\}\{m\}\}][b _ e_frac_n_m]，所以![f(k) = (1-b^\{-k\})^\{k\}][f_k_ _ _1-b_-k_k]

式子两边同时乘以f(k)得到：

![\{f'(k)\} = (1-b^\{-k\})^\{k\}ln(1-b^\{-k\}) - b^\{-k\}\\cdot lnb^\{-k\}\\cdot (1-b^\{-k\})^\{k-1\}][f_k_ _ _1-b_-k_k_ln_1-b_-k_ - b_-k_cdot lnb_-k_cdot _1-b_-k_k-1]

再令 ![t = 1 - b^\{-k\}][t _ 1 - b_-k]

所以![\{f'(t)\} = t^\{k\}lnt - (1-t)\\cdot ln(1-t)\\cdot t^\{k-1\}][f_t_ _ t_k_lnt - _1-t_cdot ln_1-t_cdot t_k-1]

提出一个![t^\{k-1\}][t_k-1]

![\{f'(t)\} = t^\{k-1\}\[tlnt - (1-t)ln(1-t)\]][f_t_ _ t_k-1_tlnt - _1-t_ln_1-t]

因为k是大于等于1的整数，b是大于1的数字，![b = e^\{\\frac\{n\}\{m\}\}][b _ e_frac_n_m] ，那么![t = 1 - b^\{-k\}][t _ 1 - b_-k]，t的取值范围就是(0,1)

那么研究![\{f'(t)\}][f_t]在(0,1)的区间里面的正负性，我们发现当t＝1/2 的时候，![\{f'(t)\} = 0][f_t_ _ 0] ，那么，咱们就来研究，这个导函数在区间![(0,\\frac\{1\}\{2\})][0_frac_1_2]和区间![\[\\frac\{1\}\{2\},1)][frac_1_2_1]的正负性。

在研究正负性之前，咱们要先研究![\{f'(t)\}][f_t]的极限和增减性。

首先来看极限：

研究函数 ![f(x) = xlnx][f_x_ _ xlnx] 和函数 ![f(x)=(1-x)ln(1-x)][f_x_1-x_ln_1-x] 的极限，因为函数![\{f'(t)\}][f_t]包含了这两种函数，所以咱们要研究它

当x -> 0+ 的时候，使用洛必达法则：

对函数![f(x) =\\frac\{lnx\}\{\\frac\{1\}\{x\}\}][f_x_ _frac_lnx_frac_1_x]  的分子![lnx][]以及分母![\\frac\{1\}\{x\}][frac_1_x] 分别求导，得到分子是![\\frac\{1\}\{x\}][frac_1_x]，分母是![\-\\frac\{1\}\{x^\{2\}\}][-_frac_1_x_2]，这时候，分别在分子和分母同时乘以![x][]，得到![\\frac\{1\}\{-\\frac\{1\}\{x\}\}][frac_1_-_frac_1_x]，即![\-x][-x] ，当x->0+ 的时候，![\-x][-x] 是趋近于0- 的，所以当x->0+ 的时候，函数 ![f(x) = xlnx][f_x_ _ xlnx] 也是无限趋近于0的，并且是负数。

x->0+ 的时候 ，函数![f(x)=(1-x)ln(1-x)][f_x_1-x_ln_1-x]，![(1-x)][1-x]是无穷趋近于1的且小于1，![ln(1-x)][ln_1-x]是无穷趋近于0的，并且小于0，那么这两个数不是0/0或者∞/∞形式的，就不适用于洛必达法则去求极限了，直接得出极限是函数![f(x)=(1-x)ln(1-x)][f_x_1-x_ln_1-x]无穷趋近于0，并且小于0，一个有限的数乘以一个无穷趋近于0的负数，结果肯定是无穷趋近于0。

那么这时候当t->0+ 的时候，![\{f'(t)\} = t^\{k-1\}\[tlnt - (1-t)ln(1-t)\]][f_t_ _ t_k-1_tlnt - _1-t_ln_1-t] ， ![t^\{k-1\} > 0][t_k-1_ _ 0] 不用说，咱们只要能够画出函数![\{g'(t)\} = tlnt - (1-t)ln(1-t)][g_t_ _ tlnt - _1-t_ln_1-t]的图像，判断函数![\{g'(t)\}][g_t]在区间(0,1)的正负性即可。

函数![\{g'(t)\}][g_t]确认了3个点：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 1][]

函数图像是怎么经过这3个点的呢？(0,0)和(1,0)是无限趋近的点。

再次对函数![\{g'(t)\}][g_t]求导：

![g''(t) = lnt + ln(1-t) + 2][g_t_ _ lnt _ ln_1-t_ _ 2]

我们通过工具，发现，这个导函数的图像是这样的：

在![(0,t\_\{0\})][0_t_0]的区间，![g''(t) < 0][g_t_ _ 0]，![\{g'(t)\}][g_t]是单调递减的，

在区间![(t\_\{0\},\\frac\{1\}\{2\})][t_0_frac_1_2] ，![g''(t) > 0][g_t_ _ 0 1]，![\{g'(t)\}][g_t]是单调递增的，

在区间![(\\frac\{1\}\{2\},t\_\{1\})][frac_1_2_t_1] ，![g''(t) > 0][g_t_ _ 0 1]，![\{g'(t)\}][g_t]是单调递增的，

在区间![(t\_\{1\},1)][t_1_1] ， ![g''(t) < 0][g_t_ _ 0]，![\{g'(t)\}][g_t]是单调递减的

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 2][]

知道函数![\{g'(t)\}][g_t]经过了![(0,0) , (\\frac\{1\}\{2\},0),(1,0)][0_0_ _ _frac_1_2_0_1_0]这三个点，(不包括(0,0)和(1,0)，只能无穷趋近这两个点)，也知道在某些区间的增减性了。

![20210410154203768.png][]

那么在![(0,\\frac\{1\}\{2\})][0_frac_1_2]区间，一定是先减后增的，图像必须这么画：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 3][]

![20210410154328108.png][]

那么在![(\\frac\{1\}\{2\},1)][frac_1_2_1 1]区间，必须是先增后减的，图像必须这么画：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 4][]

可见函数![\{g'(t)\}][g_t]在![(0,\\frac\{1\}\{2\})][0_frac_1_2]区间，![\{g'(t)\}<0][g_t_0]则![\{f'(t)\}<0][f_t_0]，![\{f(t)\}][f_t 1]单调递减，函数![\{g'(t)\}][g_t]在![(\\frac\{1\}\{2\},1)][frac_1_2_1 1]区间，![\{g'(t)\}>0][g_t_0 1]，则![\{f'(t)\}>0][f_t_0 1]，![\{f(t)\}][f_t 1]单调递增，当![t=\\frac\{1\}\{2\}][t_frac_1_2]时，![\{g'(t)\}=0][g_t_0 2]，则![\{f'(t)\}=0][f_t_0 2]

那么，当![t=\\frac\{1\}\{2\}][t_frac_1_2]时候，误判率![\{f(k)\}][f_k]取得最小值，由于![t = 1 - b^\{-k\}][t _ 1 - b_-k] ，![b = e^\{\\frac\{n\}\{m\}\}][b _ e_frac_n_m]

得出![b^\{-k\}=\\frac\{1\}\{2\}][b_-k_frac_1_2] ，![e^\{-\\frac\{n\}\{m\}\\cdot k\} = \\frac\{1\}\{2\}][e_-_frac_n_m_cdot k_ _ _frac_1_2]

![lne^\{-\\frac\{n\}\{m\}\\cdot k\} = ln\\frac\{1\}\{2\}][lne_-_frac_n_m_cdot k_ _ ln_frac_1_2]

![\\frac\{n\}\{m\}\\cdot k = ln2][frac_n_m_cdot k _ ln2]

![k = \\frac\{m\}\{n\}\\cdot ln2][k _ _frac_m_n_cdot ln2]

当知道数组长度m和插入数据量为n的时候，最优的哈希函数个数 k 为 ![\\frac\{m\}\{n\}\\cdot ln2][frac_m_n_cdot ln2] 个，（k属于正整数）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70]: /images/20221022/699d003011784c57af46ef82d7e742f2.png
[frac_1_m]: https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7Bm%7D
[1-_frac_1_m]: https://latex.codecogs.com/gif.latex?1-%5Cfrac%7B1%7D%7Bm%7D
[1-_frac_1_m_n]: https://latex.codecogs.com/gif.latex?%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bn%7D
[1-_frac_1_m_kn]: https://latex.codecogs.com/gif.latex?%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bkn%7D
[1-_1-_frac_1_m_kn]: https://latex.codecogs.com/gif.latex?1-%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bkn%7D
[1-_1-_frac_1_m_kn_2]: https://latex.codecogs.com/gif.latex?%5B1-%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bkn%7D%5D%5E%7B2%7D
[1-_1-_frac_1_m_kn_3]: https://latex.codecogs.com/gif.latex?%5B1-%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bkn%7D%5D%5E%7B3%7D
[1-_1-_frac_1_m_kn_k]: https://latex.codecogs.com/gif.latex?%5B1-%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bkn%7D%5D%5E%7Bk%7D
[f_k_ _ _1-_1-_frac_1_m_kn_k]: https://latex.codecogs.com/gif.latex?f%28k%29%20%3D%20%5B1-%281-%5Cfrac%7B1%7D%7Bm%7D%29%5E%7Bkn%7D%5D%5E%7Bk%7D
[f_k_ _ _1 - _1 - _frac_1_m_-m_cdot _frac_-kn_m_k]: https://latex.codecogs.com/gif.latex?f%28k%29%20%3D%20%5B1%20-%20%281%20-%20%5Cfrac%7B1%7D%7Bm%7D%29%5E%7B-m%5Ccdot%20%5Cfrac%7B-kn%7D%7Bm%7D%7D%5D%5E%7Bk%7D
[1 - _frac_1_m_-m]: https://latex.codecogs.com/gif.latex?%281%20-%20%5Cfrac%7B1%7D%7Bm%7D%29%5E%7B-m%7D
[f_k_ _ _1-e_-_frac_n_m_cdot k_k]: https://latex.codecogs.com/gif.latex?f%28k%29%20%3D%20%281-e%5E%7B-%5Cfrac%7Bn%7D%7Bm%7D%5Ccdot%20k%7D%29%5E%7Bk%7D
[lnf_k_ _ ln_1-e_-_frac_n_m_cdot k_k]: https://latex.codecogs.com/gif.latex?lnf%28k%29%20%3D%20ln%281-e%5E%7B-%5Cfrac%7Bn%7D%7Bm%7D%5Ccdot%20k%7D%29%5E%7Bk%7D
[lnf_k_ _ k_cdot ln_1-e_-_frac_n_m_cdot k]: https://latex.codecogs.com/gif.latex?lnf%28k%29%20%3D%20k%5Ccdot%20ln%281-e%5E%7B-%5Cfrac%7Bn%7D%7Bm%7D%5Ccdot%20k%7D%29
[b _ e_frac_n_m]: https://latex.codecogs.com/gif.latex?b%20%3D%20e%5E%7B%5Cfrac%7Bn%7D%7Bm%7D%7D
[lnf_k_ _ k_cdot ln_1-b_-k_k]: https://latex.codecogs.com/gif.latex?lnf%28k%29%20%3D%20k%5Ccdot%20ln%281-b%5E%7B-k%7D%29%5E%7Bk%7D
[frac_1_f_k_cdot _f_k_ _ ln_1-b_-k_k_cdot _frac_1_1-b_-k_cdot _-b_-k_cdot lnb_cdot _-1]: https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7Bf%28k%29%7D%5Ccdot%20%7Bf%27%28k%29%7D%20%3D%20ln%281-b%5E%7B-k%7D%29&plus;k%5Ccdot%20%5Cfrac%7B1%7D%7B1-b%5E%7B-k%7D%7D%5Ccdot%20%28-b%5E%7B-k%7D%5Ccdot%20lnb%5Ccdot%20%28-1%29%29
[frac_1_f_k_cdot _f_k_ _ ln_1-b_-k_frac_k_cdot b_-k_cdot lnb_1-b_-k]: https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7Bf%28k%29%7D%5Ccdot%20%7Bf%27%28k%29%7D%20%3D%20ln%281-b%5E%7B-k%7D%29&plus;%5Cfrac%7Bk%5Ccdot%20b%5E%7B-k%7D%5Ccdot%20lnb%7D%7B1-b%5E%7B-k%7D%7D
[f_k_ _ _1-b_-k_k]: https://latex.codecogs.com/gif.latex?f%28k%29%20%3D%20%281-b%5E%7B-k%7D%29%5E%7Bk%7D
[f_k_ _ _1-b_-k_k_ln_1-b_-k_ - b_-k_cdot lnb_-k_cdot _1-b_-k_k-1]: https://latex.codecogs.com/gif.latex?%7Bf%27%28k%29%7D%20%3D%20%281-b%5E%7B-k%7D%29%5E%7Bk%7Dln%281-b%5E%7B-k%7D%29%20-%20b%5E%7B-k%7D%5Ccdot%20lnb%5E%7B-k%7D%5Ccdot%20%281-b%5E%7B-k%7D%29%5E%7Bk-1%7D
[t _ 1 - b_-k]: https://latex.codecogs.com/gif.latex?t%20%3D%201%20-%20b%5E%7B-k%7D
[f_t_ _ t_k_lnt - _1-t_cdot ln_1-t_cdot t_k-1]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D%20%3D%20t%5E%7Bk%7Dlnt%20-%20%281-t%29%5Ccdot%20ln%281-t%29%5Ccdot%20t%5E%7Bk-1%7D
[t_k-1]: https://latex.codecogs.com/gif.latex?t%5E%7Bk-1%7D
[f_t_ _ t_k-1_tlnt - _1-t_ln_1-t]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D%20%3D%20t%5E%7Bk-1%7D%5Btlnt%20-%20%281-t%29ln%281-t%29%5D
[f_t]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D
[f_t_ _ 0]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D%20%3D%200
[0_frac_1_2]: https://latex.codecogs.com/gif.latex?%280%2C%5Cfrac%7B1%7D%7B2%7D%29
[frac_1_2_1]: https://latex.codecogs.com/gif.latex?%5B%5Cfrac%7B1%7D%7B2%7D%2C1%29
[f_x_ _ xlnx]: https://latex.codecogs.com/gif.latex?f%28x%29%20%3D%20xlnx
[f_x_1-x_ln_1-x]: https://latex.codecogs.com/gif.latex?f%28x%29%3D%281-x%29ln%281-x%29
[f_x_ _frac_lnx_frac_1_x]: https://latex.codecogs.com/gif.latex?f%28x%29%20%3D%5Cfrac%7Blnx%7D%7B%5Cfrac%7B1%7D%7Bx%7D%7D
[lnx]: https://latex.codecogs.com/gif.latex?lnx
[frac_1_x]: https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7Bx%7D
[-_frac_1_x_2]: https://latex.codecogs.com/gif.latex?-%5Cfrac%7B1%7D%7Bx%5E%7B2%7D%7D
[x]: https://latex.codecogs.com/gif.latex?x
[frac_1_-_frac_1_x]: https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7B-%5Cfrac%7B1%7D%7Bx%7D%7D
[-x]: https://latex.codecogs.com/gif.latex?-x
[1-x]: https://latex.codecogs.com/gif.latex?%281-x%29
[ln_1-x]: https://latex.codecogs.com/gif.latex?ln%281-x%29
[t_k-1_ _ 0]: https://latex.codecogs.com/gif.latex?t%5E%7Bk-1%7D%20%3E%200
[g_t_ _ tlnt - _1-t_ln_1-t]: https://latex.codecogs.com/gif.latex?%7Bg%27%28t%29%7D%20%3D%20tlnt%20-%20%281-t%29ln%281-t%29
[g_t]: https://latex.codecogs.com/gif.latex?%7Bg%27%28t%29%7D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 1]: /images/20221022/cb900c24f63144caadb8ef38ae862c9e.png
[g_t_ _ lnt _ ln_1-t_ _ 2]: https://latex.codecogs.com/gif.latex?g%27%27%28t%29%20%3D%20lnt%20&plus;%20ln%281-t%29%20&plus;%202
[0_t_0]: https://latex.codecogs.com/gif.latex?%280%2Ct_%7B0%7D%29
[g_t_ _ 0]: https://latex.codecogs.com/gif.latex?g%27%27%28t%29%20%3C%200
[t_0_frac_1_2]: https://latex.codecogs.com/gif.latex?%28t_%7B0%7D%2C%5Cfrac%7B1%7D%7B2%7D%29
[g_t_ _ 0 1]: https://latex.codecogs.com/gif.latex?g%27%27%28t%29%20%3E%200
[frac_1_2_t_1]: https://latex.codecogs.com/gif.latex?%28%5Cfrac%7B1%7D%7B2%7D%2Ct_%7B1%7D%29
[t_1_1]: https://latex.codecogs.com/gif.latex?%28t_%7B1%7D%2C1%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 2]: /images/20221022/5ff07862d9d141c28b52ec5a7307b933.png
[0_0_ _ _frac_1_2_0_1_0]: https://latex.codecogs.com/gif.latex?%280%2C0%29%20%2C%20%28%5Cfrac%7B1%7D%7B2%7D%2C0%29%2C%281%2C0%29
[20210410154203768.png]: /images/20221022/2453bef70b354aae8083820029d6cf70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 3]: /images/20221022/7ff86820fbf64c61921f9507af17ee52.png
[20210410154328108.png]: /images/20221022/754a081da81f45bab4609515d8e96cc2.png
[frac_1_2_1 1]: https://latex.codecogs.com/gif.latex?%28%5Cfrac%7B1%7D%7B2%7D%2C1%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1hlb25fQ0M_size_16_color_FFFFFF_t_70 4]: /images/20221022/db766084a52e4cb2a7488ac6c74747ed.png
[g_t_0]: https://latex.codecogs.com/gif.latex?%7Bg%27%28t%29%7D%3C0
[f_t_0]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D%3C0
[f_t 1]: https://latex.codecogs.com/gif.latex?%7Bf%28t%29%7D
[g_t_0 1]: https://latex.codecogs.com/gif.latex?%7Bg%27%28t%29%7D%3E0
[f_t_0 1]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D%3E0
[t_frac_1_2]: https://latex.codecogs.com/gif.latex?t%3D%5Cfrac%7B1%7D%7B2%7D
[g_t_0 2]: https://latex.codecogs.com/gif.latex?%7Bg%27%28t%29%7D%3D0
[f_t_0 2]: https://latex.codecogs.com/gif.latex?%7Bf%27%28t%29%7D%3D0
[f_k]: https://latex.codecogs.com/gif.latex?%7Bf%28k%29%7D
[b_-k_frac_1_2]: https://latex.codecogs.com/gif.latex?b%5E%7B-k%7D%3D%5Cfrac%7B1%7D%7B2%7D
[e_-_frac_n_m_cdot k_ _ _frac_1_2]: https://latex.codecogs.com/gif.latex?e%5E%7B-%5Cfrac%7Bn%7D%7Bm%7D%5Ccdot%20k%7D%20%3D%20%5Cfrac%7B1%7D%7B2%7D
[lne_-_frac_n_m_cdot k_ _ ln_frac_1_2]: https://latex.codecogs.com/gif.latex?lne%5E%7B-%5Cfrac%7Bn%7D%7Bm%7D%5Ccdot%20k%7D%20%3D%20ln%5Cfrac%7B1%7D%7B2%7D
[frac_n_m_cdot k _ ln2]: https://latex.codecogs.com/gif.latex?%5Cfrac%7Bn%7D%7Bm%7D%5Ccdot%20k%20%3D%20ln2
[k _ _frac_m_n_cdot ln2]: https://latex.codecogs.com/gif.latex?k%20%3D%20%5Cfrac%7Bm%7D%7Bn%7D%5Ccdot%20ln2
[frac_m_n_cdot ln2]: https://latex.codecogs.com/gif.latex?%5Cfrac%7Bm%7D%7Bn%7D%5Ccdot%20ln2