1、离线算法
算法先获取到完整的数据再进行数据的处理，同时算法可以以任意顺序访问数据。
2、在线算法
算法一次只能接收一个或者一批输入，这意味着我们必须在对未来一无所知时对当前每个元素进行决策，同时在此过程中做出的决定不可撤销，其形式比较类似于数据流模型。
2.1竞争率(Competitive Ratio)
最优离线算法的概念相对容易理解，即离线算法中可以达到最好效果的算法，针对离线算法当然也可以采用贪心等思想来解决，但是贪心往往不能在离线处理的过程中达到时空的最优。
当前最小化在线算法指的是，使用的在线算法的最坏可能，比如贪心算法往往被认为不是最优的，同时贪心算法根据初始化不同可能产生不同的结果，假设使用某种贪心算法作为在线算法，则最小化的在线算法就是指贪心算法中最坏的情况
2.2Web广告的二分图匹配
我们可以将广告与搜索查询的匹配问题可以抽象简化为二分图匹配问题，假设我们已知广告商与搜索关键字之间的关系如下：{(1,a), (1,c), (2,b), (3,b), (3,d), (4,a)}
在讨论二分图匹配的在线算法之前，我们首先对于几个概念有以下定义：
匹配：一个由边构成的子集。
完美匹配：如果对于上述这些边而言满足，1.任何一个节点都不会同时是两条或多条边的端点。2.所有的节点都出现在这个匹配中。可以称这个匹配是完美匹配，但是需要注意的是，当且仅当左集合和右集合中的节点个数一样时才可能出现完美匹配。图示的完美匹配集合为：{(1,c), (2,b), (3,d), (4,a)}
最大匹配：所有匹配中最大的匹配，所有完美匹配都是最大匹配。
最大匹配贪心算法：按照任意但确定的次序来考虑边。当考虑边(x,y)时，如果x和y都不是已有匹配中边的端点，则将其加入，否则跳过。
对于图例中，假定按照节点的词典顺序贪心，最终选出的序列为{(1, a),(2, b),(3, d)}，显然非最大匹配
3、上界的证明
如果贪心算法以{(1,a), (3,b)}开始贪心，则后续没有任何边可以加入集合，此时竞争率为2/4，且找不到比此种顺序更差的贪心顺序。
由于算法的竞争率是算法在所有可能的输入下所得到的最小值和最优结果的比值，因此我们知道1/2是竞争率的上界。
3.1 Balance算法的上界证明、
对于广告商 A 和 B:
A对查询x投标，A的预算为2
B对查询x与y投标，B的预算为2
假设当月的搜索序列为: x x y y
Balance算法: B A B _ 或者 A B B _
最优离线策略: A A B B
c <= 3/4
3.2.2.2 Balance算法的下界证明
假设有两个广告商A1和A2，预算都是B。假定每个查询都会按照最优算法的结果分配给相应的广告商。再假定两个广告商的预算都被最优算法花光。否则，我们可以降低预算。则对于最优离线算法，我们可以画出示意图如下，注意此时分配给A1和A2的查询的颜色。
因为在最优离线算法下，我们有A1和A2的均等分配，所以易得：Balance算法必须用尽至少一位广告商的预算。否则，我们就在二者都还有预算的情况下，对某次查询没有进行分配。
此时根据Balance算法我们可以做出分配图如下：
显然，如上论证，Balance算法必须用尽至少一位广告商的预算。否则，我们就在二者都还有预算的情况下，对某次查询没有进行分配，与最优算法中每次查询都至少有一位广告商出价相互矛盾。
因此，假设A2已经被分配了B个查询，这些查询在最优算法下不一定全部属于原来的A2。同时令A1被分配到的总数为y，x=B-y代表在Balance算法中未被分配的查询。
此时计算Balance算法的下界，目标就转化为了证明：y>=x，则可以保证c>=3/4
Balance算法的分配在此时可以分为两种情况，这取决于是否有更多在最优算法中分配给A1的查询会在Balance算法中分配给A1或者A2
