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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

1: def binary_min(arr):
2: if len(arr) == 1:
3: return arr[0]
4: else:
5: mid = len(arr)//2
6: min1 = binary_min(arr[0:mid])
7: min2 = binary_min(arr[mid:len(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)

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

回帖奖励 +3 鱼币