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