使用第n个元素得到第100个元素O(n) 迭代第二次，但只有一次，并输出大于此特定元素的所有元素。

请特别注意，第二步可能很容易并行计算!当你需要一百万个最大的元素时，它也会很有效。

The simplest solution is to scan the billion numbers large array and hold the 100 largest values found so far in a small array buffer without any sorting and remember the smallest value of this buffer. First I thought this method was proposed by fordprefect but in a comment he said that he assumed the 100 number data structure being implemented as a heap. Whenever a new number is found that is larger then the minimum in the buffer is overwritten by the new value found and the buffer is searched for the current minimum again. If the numbers in billion number array are randomly distributed most of the time the value from the large array is compared to the minimum of the small array and discarded. Only for a very very small fraction of number the value must be inserted into the small array. So the difference of manipulating the data structure holding the small numbers can be neglected. For a small number of elements it is hard to determine if the usage of a priority queue is actually faster than using my naive approach.

I want to estimate the number of inserts in the small 100 element array buffer when the 10^9 element array is scanned. The program scans the first 1000 elements of this large array and has to insert at most 1000 elements in the buffer. The buffer contains 100 element of the 1000 elements scanned, that is 0.1 of the element scanned. So we assume that the probability that a value from the large array is larger than the current minimum of the buffer is about 0.1 Such an element has to be inserted in the buffer . Now the program scans the next 10^4 elements from the large array. Because the minimum of the buffer will increase every time a new element is inserted. We estimated that the ratio of elements larger than our current minimum is about 0.1 and so there are 0.1*10^4=1000 elements to insert. Actually the expected number of elements that are inserted into the buffer will be smaller. After the scan of this 10^4 elements fraction of the numbers in the buffer will be about 0.01 of the elements scanned so far. So when scanning the next 10^5 numbers we assume that not more than 0.01*10^5=1000 will be inserted in the buffer. Continuing this argumentation we have inserted about 7000 values after scanning 1000+10^4+10^5+...+10^9 ~ 10^9 elements of the large array. So when scanning an array with 10^9 elements of random size we expect not more than 10^4 (=7000 rounded up) insertions in the buffer. After each insertion into the buffer the new minimum must be found. If the buffer is a simple array we need 100 comparison to find the new minimum. If the buffer is another data structure (like a heap) we need at least 1 comparison to find the minimum. To compare the elements of the large array we need 10^9 comparisons. So all in all we need about 10^9+100*10^4=1.001 * 10^9 comparisons when using an array as buffer and at least 1.000 * 10^9 comparisons when using another type of data structure (like a heap). So using a heap brings only a gain of 0.1% if performance is determined by the number of comparison. But what is the difference in execution time between inserting an element in a 100 element heap and replacing an element in an 100 element array and finding its new minimum?

在理论层面:在堆中插入需要多少比较。我知道它是O(log(n))但常数因子有多大呢?我 在机器级别:缓存和分支预测对堆插入和数组中线性搜索的执行时间有什么影响? 在实现级别:库或编译器提供的堆数据结构中隐藏了哪些额外成本?

我认为，在人们试图估计100个元素堆和100个元素数组的性能之间的真正区别之前，这些都是必须回答的一些问题。所以做一个实验并测量真实的表现是有意义的。

求n个元素中最大的m个元素，其中n >>> m

最简单的解决方案，每个人都应该很明显，就是简单地做m次冒泡排序算法。

然后打印出数组的最后n个元素。

它不需要外部数据结构，并且使用了一种大家都知道的算法。

运行时间估计为O(m*n)。到目前为止最好的答案是O(nlog (m))，所以这个解决方案对于小m来说并不显着昂贵。

我并不是说这不能改进，但这是迄今为止最简单的解决方案。

Time ~ O(100 * N)
Space ~ O(100 + N)

创建一个包含100个空槽的空列表 对于输入列表中的每个数字: 如果数字小于第一个，跳过 否则用这个数字代替它 然后，将数字通过相邻的交换;直到它比下一个小 返回列表

注意:如果log(input-list.size) + c < 100，那么最佳的方法是对输入列表进行排序，然后拆分前100项。

此代码用于在未排序数组中查找N个最大的数字。

#include <iostream>


using namespace std;

#define Array_Size 5 // No Of Largest Numbers To Find
#define BILLION 10000000000

void findLargest(int max[], int array[]);
int checkDup(int temp, int max[]);

int main() {


        int array[BILLION] // contains data

        int i=0, temp;

        int max[Array_Size];


        findLargest(max,array); 


        cout<< "The "<< Array_Size<< " largest numbers in the array are: \n";

        for(i=0; i< Array_Size; i++)
            cout<< max[i] << endl;

        return 0;
    }




void findLargest(int max[], int array[])
{
    int i,temp,res;

    for(int k=0; k< Array_Size; k++)
    {
           i=0;

        while(i < BILLION)
        {
            for(int j=0; j< Array_Size ; j++)
            {
                temp = array[i];

                 res= checkDup(temp,max);

                if(res == 0 && max[j] < temp)
                    max[j] = temp;
            }

            i++;
        }
    }
}


int checkDup(int temp, int max[])
{
    for(int i=0; i<N_O_L_N_T_F; i++)
    {
        if(max[i] == temp)
            return -1;
    }

    return 0;
}

这可能不是一个有效的方法，但可以完成工作。

希望这能有所帮助

你可以遍历这些数字，需要O(n)

只要发现一个大于当前最小值的值，就将新值添加到一个大小为100的循环队列中。

循环队列的最小值就是新的比较值。继续往队列中添加。如果已满，则从队列中提取最小值。