我对big-O的了解是有限的,当日志术语出现在等式中时,它会让我更加惊讶.
有人可以用简单的语言向我解释O(log n)算法是什么吗？对数来自哪里？
当我试图解决这个中期练习题时,这个问题就出现了:
设X(1..n)和Y(1..n)包含两个整数列表,每个整数按非递减顺序排序.给出O(log n)-time算法以找到所有2n个组合元素的中值(或第n个最小整数).例如,X =(4,5,7,8,9)和Y =(3,5,8,9,10),那么7是组合列表的中位数(3,4,5,5,7) ,8,8,9,9,10).[提示:使用二分搜索的概念]