0

下面的代码是找出一个数字在数组中显示的次数。例如：

1,2,2,2,3,4,5,5,5,5 number 2 = 3 times number 5 = 4 times.

以下代码在 Java 中的时间复杂度是多少？就时间复杂度而言，解决此问题的最佳方法是什么？

public static void main(String[]args)
    {
        int[] data = {1,1,2,3,4,4,4,5,6,7,8,8,8,8};
        System.out.println(count(data,8));


    }


public static int count(int[] a, int x)
{
    int count=0;
    int index=0;
    while(index<a.length)
    {
        if(a[index]==x)
        {
            count++;
        }
        index++;

    }
    return count;
}
4

6 回答 6

3

是 o(n) ，logN 还是其他？

您查看每个元素一次，因此它是 O(n)

如果是 o(n)，我可以通过 LogN 同谋来完成这项任务吗？

使用低值和高值进行二分搜索，搜索的值刚好小于您搜索的值并略高于您搜索的值。这两个结果之间的差异将告诉您有多少。这是一个 O(Log N) 搜索。

于 2013-01-06T09:43:05.387 回答
1

while(index<a.length)

此循环在 中的每个值运行一次data。这是O(n)。如果您想在O(log n)中执行此操作，您将需要一个排序数组和一个二进制搜索。你有一个排序数组，所以你只需要做一个二进制搜索。

于 2013-01-06T09:42:34.700 回答
1

答案是O(n)。

您遍历数组，查看每个索引一次。

例如，数组大小是 10 --> 10 次比较，数组大小是 100 --> 100 次比较等等。

于 2013-01-06T09:42:43.587 回答
1

您检查数组的每个元素，因此您的代码具有O(n)时间复杂度。

要及时做到这一点O(log n)，您必须利用数组已排序的事实。这可以通过二进制搜索的变体来完成。由于这看起来像家庭作业，因此在提供更多提示之前，我会让您考虑一下。

于 2013-01-06T09:42:46.310 回答
0

O(n)。当代码遍历数组的每个元素时，它的 0(n)。

于 2013-01-06T10:17:12.990 回答
0

O(n) 此代码使用数组的每个元素。

while(index<a.length)

您可以将其替换为

for(int index = 0; index < a.length; i++)
于 2013-01-06T09:44:42.617 回答