最好的情况下，大O的复杂性 [英] Best case Big O complexity

问题描述

问题：
你怎么能限制输入数据，以达到更好的大O的复杂性？描述一个算法来处理这​​有限的数据，以寻找是否有任何重复。什么是大O的复杂性？的（通过限制数据，是指数据的大小/阵列）。

The question:
how can you limit the input data to achieve a better Big O complexity? Describe an algorithm for handling this limited data to find if there are any duplicates. What is the Big O complexity? (By limiting data, we mean size of data/ array).

有我需要帮助我实现该任务的解决方案。我已经打消了我答案，我张贴，因为它们不是necessary-感谢您的帮助家伙：）

Got the solutions i needed to help me achieve the task. I've removed my answers that i posted since they weren't necessary- thanks for your help guys :)

推荐答案

可以达到更好的大O的复杂性，如果你知道的最大值的整数数组可以采取。可以说，它为m。 该算法来做到这一点是桶排序的方差。的复杂度为O（N）。 来源$ C ​​$算法的C：

You can achieve a better big O complexity if you know the max value your integer array can take. Lets say it as m. The algorithm to do it is the variance of Bucket Sort. The complexity is O(n). Source code of algorithm:

public boolean HasDuplicates(int [] arr, int m)
{

    boolean bucket[] = new boolean[m];

    for (int elem : arr)
    {

        if (bucket[elem])
        {
           return true; // a duplicate found
        }

        bucket[elem] = true;
    }   
    return false;   
}

这篇关于最好的情况下，大O的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！