二分查找是一个非常基础的算法，但是每次写边界总要想一下，特别是用二分查找来寻找上下界的时候。

问题描述

问题：有一段很长整数流，不知道其长度，内存可能也不够存下所有数据。希望从这个整数流中抽样出$k$个整数，要求每个整数被抽样的概率相同。

这种问题称之为蓄水池抽样问题。

本文中默认对数组从小到大排序，数组大小为$n$。

基于比较的排序算法

基于比较的排序算法最坏时间复杂度下界是$O(nlgn)$，这是钛合金天花板，突破不了。

Tarjan算法可用于求图的割点，割边，连通分量。本文对hihocoder上52~55周关于tarjan算法的内容进行一个总结。

割点，割边与Tarjan

在介绍tarjan算法之前有必要知道割边与割点的概念。
割边：在连通图中，如果删除了某条边后该图不再连通，则称这样的边为割边或桥
割点：在连通图中，如果删除了某个点及与这个点相连的边后该图不再连通，则称这样的点为割点

为什么要读《代码整洁之道》

作为一个写了多年代码的程序猿，对“最痛苦的事情莫过于读别人写的代码”深有体会。事实上，即使是自己写的代码过段时间再去读也同样痛苦不堪。希望通过学习这本书，让以后写出来的代码更具有易读性。方便自己，方便他人。

广义线性模型

上一篇文章中介绍了线性模型：

$$y = \theta ^ \mathrm{T} x \tag{1}$$

该模型虽然简单，但却富于变化。例如，假设样例对应的输出在指数上变化，我们可以将输出的对数作为逼近目标得到对数回归模型，即：

$$\ln{y} = \theta ^ \mathrm{T} x \tag{2}$$

更一般地，考虑单调可微函数 $ f(\cdot) $，令

$$y = f ^ {-1} (\theta ^ \mathrm{T} x) \tag{3}$$

即可得到广义线性模型。其中 $ f(\cdot) $ 的作用是联系模型输出与样例真实标记，称之为联系函数。

线性回归问题描述

对于这个问题，举个实际例子更好理解：你想购买一套房子，现知道这套房子的面积和一些数据，这些数据包括一些房子的面积大小和售价，假如房子的面积 $x$ 和售价 $y$ 存在线性关系 $y = ax + b$，那么根据历史数据求出这个线性关系中的 $a$ 和 $b$ 就是一个最简单一维的线性回归问题。求出这个 $y = ax + b$后，代入当前房子的面积即可估算出当前房子的售价。

题目及分析

给一个非空 $ r \times c$ 的矩阵 $ r>>c $，找一个子矩阵使得该矩阵的和不超过给定的 $ k $（难度：hard）

暴力方法： 枚举两个子矩阵的两个端点，复杂度 $ O(r^2c^2) $
这个问题是另外几个问题的叠加

一直以为网络世界是平行于现实世界的另一个世界，那个世界比现实世界更辽阔。每一个可以访问的域名就是某个或某群人的领土。而今我也买了一个域名，并建起了可以访问的网站，如此开疆辟土之大事自然需要一篇序来讲清来龙去脉。