加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 百科 > 正文

巧妙地计算数组中的位置(C)

发布时间:2020-12-16 09:57:48 所属栏目:百科 来源:网络整理
导读:为了性能,在O(n ^ 2)算法中,我希望将复杂度降低两倍.基本上,我有这种形状的结构: 0 1 2 3 4 5----------------------0 | 11,2 | 23,4,5 | 36,7,8,9 | 410,11,12,13,14 | 515,16,17,18,19,20| 6 因此,我创建了一个大小为((1 n)* n / 2)的向量 – 显然,算术和
为了性能,在O(n ^ 2)算法中,我希望将复杂度降低两倍.基本上,我有这种形状的结构:

0   1   2   3   4   5
----------------------
0                     | 1
1,2                 | 2
3,4,5             | 3
6,7,8,9         | 4
10,11,12,13,14    | 5
15,16,17,18,19,20| 6

因此,我创建了一个大小为((1 n)* n / 2)的向量 – 显然,算术和.问题是我现在需要来回计算每个位置.例如,如果我想计算第2列和第5行中的位置,我可以像这样计算:

int get_position(int x,int y)
{
    int smaller = min(x,y);
    int greater = max(x,y);
    return ((1 + greater) * greater / 2) - greater + smaller;
}

问题是:我怎么能算回来的呢?换句话说,例如从位置号. 17我想得到2和6.

或者,也许有更好的方法在C中做到这一点? (有些结构会让事情变得简单)

编辑
我正在寻找一种在O(1)中计算的方法.它存在吗?

解决方法

是的,确实存在O(1)解决方案.

在数学上,更大的指数是:

i = [sqrt(2n + 1/4) + 1/2]

(方括号“[]”表示截断为整数).

但是,在浮点中正确计算它可能很困难.

那么较小的索引就是:

j = n - i*(i-1) / 2

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读