巧妙地计算数组中的位置(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)解决方案.
在数学上,更大的指数是: i = [sqrt(2n + 1/4) + 1/2] (方括号“[]”表示截断为整数). 但是,在浮点中正确计算它可能很困难. 那么较小的索引就是: j = n - i*(i-1) / 2 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |