数据结构课程中索引搜索时间复杂度表述疑问：T(n)-log(n)是否为笔误？

你完全不用抱歉，基础概念抠细节才是学好数据结构的关键！你的判断非常准确——笔记里写的T(n)-log(n)几乎可以肯定是笔误，正确的表述应该是T(n)=O(log n)（或者更严谨的T(n)=Θ(log n)）。

具体来说：

• 当我们有一个按字母顺序排列的有序姓名索引时，最常用的高效搜索方法是二分查找（Binary Search）。
• 二分查找每次都能把搜索范围缩小一半，所以最坏情况下的时间复杂度是对数级的，也就是和log(n)成正比，用渐近符号表示就是O(log n)（大O表示上界）或者Θ(log n)（大Θ表示紧界）。
• 笔记里的减号很大概率是输入错误，应该是等号；也有可能是排版时符号错位导致的。

总之你的疑惑完全合理，能注意到这个细节说明你在认真思考，继续保持这种严谨的学习态度就好！

内容的提问来源于stack exchange，提问作者Placeholder