我已经理解它是二次的，但我正在参加离散数学的多项选择练习测试，只有四个选项是：
a) 对数
b) 线性的
c) 线性的
d)多项式
问问题
174 次
2 回答
1
a) 对数 = O(log n)
b) 线性 = O(n)
c) 线性 = O(n log n)
d) 多项式 = O(n k )
所以 O(n 2 ) 是多项式的。
于 2013-02-25T08:28:40.130 回答
0
将新值插入到排序值的列表或树中是 O(log n)。
使用直接排序列表最容易看到。假设您要插入 x。找到 [n/2] 处的值。如果这大于 x，则正确的位置位于左半边。如果 [n/2] 小于 x，则正确的位置位于右侧。重复，每次检查中间值。每一步都会将要检查的间隔大小减半，直到找到正确的值，从而为插入提供对数时间。
插入树是类似的；你必须遍历树到正确的节点位置，这需要遍历树的平均深度，它与log n成正比
于 2013-02-28T09:35:36.083 回答