[背景音乐] 翻译: RyukaSuu |审阅: 19waa Coursera Global Translator Community
我们已经学习了最近邻搜索
并详细描述了它的算法
接着我们讨论了算法中的两个关键点
一是，我们如何表示文档？
二是，
我们如何计算两篇文章的距离
然后我们指出这两点对算法性能至关重要
但现在，我想分析下最近邻搜索的计算量
我们把这称为搜索复杂度
那么，暴力搜索的复杂度是多少呢？
假设我们有一个待查询点
接下来怎么做？
我们要逐个扫描语料库中的文档
计算待查询点和每篇文章的距离
求出最小值
这个方法的复杂度是多少？
对一个1-NN查询请求，我们要计算N个不同的距离
所以复杂度是O(N)，N是语料库中的文章数
如果要做k近邻查询
并返回k篇最相近的文章，那么复杂度是O(N log k)
O(logk)源于
如果使用优先队列保存前k个值，每次插入的复杂度是O(log k)
但是，如果N的值很大呢？
如果你需要在同一个语料库上做多次查询呢？
我们能不能在暴力搜索的基础上有所改进呢？
[背景音乐] 翻译: RyukaSuu |审阅: 19waa Coursera Global Translator Community