objective-c - 如何最小化数组访问次数

Question

如何减少访问数组的时间，目前它访问数组2次以找到用户提供的数字序列中的最大数字，

int i=0;
    int max = -1;
    int a_i = -1;

    for (i=0; i<length; i++)
    {   
    a_i = array(a,i);

    if (a_i > max) 
    {
    max = a_i;
    }

    return max;

完整代码on pastebin

感谢任何帮助。

Answer 1

• 简短回答

你不能，考虑到你没有关于数组的信息，你必须迭代每个项目。

• 长答案

如果您接受之前损失一些时间，则可以减少阅读时的访问量

使用数组，您需要 O(n) 来插入(everyting)，并 O(n) 来查找最小值

如果您真正想要的是减少查找函数所花费的时间，您可以使用 minimum heap ，您在插入时会产生一些开销 O(n log(n)) 但只需要 O(1) 进行搜索。

您还可以在搜索之前对数组进行排序，这可以是O(n log n)