JINNINGXIAN 发表于 2020-10-23 06:58:29

求问一下，关于代码的时间复杂度

1: def binary_min(arr):
2: if len(arr) == 1:
3: return arr
4: else:
5: mid = len(arr)//2
6: min1 = binary_min(arr)
7: min2 = binary_min(arr)
8: if min1 < min2:
9: return min1
10: else:
11: return min2


想问问 line 8的时间复杂度基于 对比数量 （我认为 是 O(log n) ）

还有这个 功能整体的时间复杂度 （我认为 是 O(n) ）

xieglt 发表于 2020-10-23 07:42:34

这两段代码一模一样，都是两分法递归。时间复杂度都是O(LOGN)

JINNINGXIAN 发表于 2020-10-23 07:57:06

xieglt 发表于 2020-10-23 07:42
这两段代码一模一样，都是两分法递归。时间复杂度都是O(LOGN)

想问一下，那第八行执行的次数的时间复杂度呢

xieglt 发表于 2020-10-23 08:35:10

本帖最后由 xieglt 于 2020-10-23 08:38 编辑

JINNINGXIAN 发表于 2020-10-23 07:57
想问一下，那第八行执行的次数的时间复杂度呢

一条IF指令O（1）

看错了，是数组比较，如果是C语言实现的话，应该是O（N/2)*O(LOGN)
页: [1]
查看完整版本: 求问一下，关于代码的时间复杂度