用C总结数组 [英] Summing up array in C

查看:114
本文介绍了用C总结数组的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

有没有办法对C中的O(1)时间中从位置A到B的数组元素进行汇总?

假设我们有一个数组,我们想要找到从A到B的一些元素.复杂度为O(n).

Is there any way to sum up an array elemnets from position A to B in O(1) time in C?

Lets say we have an array and we want to find the some of elemnts from A to B. The complexity is O(n).

int sum_array(int* array,int start, int end)
{
    int i = start;
    int res = 0;
   while (i != end) {
       res += array[i];
       i++;
   }
    return res;
}

int main() {
    int array[10] = { 2,6,9,4,2,64,5,9,54,3 };
    int A = 3;
    int B = 8;
    
    int Sum = sum_array(array,A,B);
    
    //sum is 138!
}









Is there any way to make it O(1)?

推荐答案

对于随机数数组,您无法获得恒定的复杂度O(1)而是O (n).
如果您有一个数字序列的数组(1、2、3、4、5 ...),则可以使用O(1)来计算总和.
For an array of random numbers you can''t achieve constant complexity O(1) but rather O(n).
If you have an array of a number sequence (1, 2, 3, 4, 5 ...) the sum can be computed with O(1).


这篇关于用C总结数组的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆