gpt4 book ai didi

algorithm - 在固定的时间内找到元素的索引 O(1)

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:53:39 25 4
gpt4 key购买 nike

我花了一个小时试图解决这个问题,但找不到任何方法。问题如下:

一个排序列表,长度N。列表中可能有重复项。给定一个元素 x,您需要在列表中找到 x 的最新索引。如果 x 不存在,则返回相关消息。

注意:模型是 CREW(并发读取独占写入)- 表示允许并发读取,但写入是独占的,表示不允许并发写入。

1) 描述一个使用 N 个 CPU 并在固定时间内解决问题的并行算法(我猜他们的意思是 O(1))。

2) 解释为什么所描述的算法是正确的。

最佳答案

我假设输入是一个 0 索引、排序(递增)的数组 A[],长度为 N

用值 UNSET 初始化共享结果变量:

RESULT := "UNSET"

用以下程序启动N个CPU,由i参数化(从0N-1) :

CPU(i):
if i==0 and A[0] > x {
RESULT = "NO SOLUTION"
} else if A[i] == x and (i + 1 == N or A[i+1] > x) {
RESULT = i
} else if A[i] < x and (i + 1 == N or A[i+1] > x) {
RESULT = "NO SOLUTION"
}

RESULT 更新后程序终止。

请注意,只有一个 CPU 写入 RESULT(因为输入已排序),因此永远不会有并发写入,但除了第一个之外的每个数组位置都由两个 CPU 读取。每个 CPU 执行固定量的工作,因此程序会在固定的时间内终止。

关于algorithm - 在固定的时间内找到元素的索引 O(1),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43429357/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com