小编Set*_*eno的帖子

我正在研究测试并发现了这个问题:

我无法确定复杂性,我认为它是O(n ²)或O(n ³)而我倾向于O(n ³).
有人能告诉我它是什么以及为什么？

我认为它是O(n ²)是因为在j循环中,j = i它给出了一个三角形的形状,然后k循环从i + 1到j,我认为是三角形的另一半.

public static int what(int[] arr)
{
    int m = arr[0];
    for (int i=0; i<arr.length; i++)
    {
        for (int j=i; j<arr.length;j++)
        {
            int s = arr[i];
            for (int k=i+1; k<=j; k++)
             s += arr[k];
            if (s > m)
             m = s;
        }
    }
    return m;
}

如果你能告诉我它的作用吗？

我想它返回正整数的加法或数组中的最大整数.
但对于像{99, -3, 0, 1}它这样的数组返回99 …

我正在学习考试,并发现了这个问题.

您将获得一个排序的整数数组,例如:

{-5, -5, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 67, 67, 99}

写一个方法:

Public static int count (int[] a, int x)

返回数字'x'在数组中的次数.

例如:

x = -5, it returns 2
x = 2, it returns 5
x = 8, it returns 0

我需要尽可能高效地写它,请不要给我答案(或者如果你愿意的话写下来,但我不会看),我的想法是做二分搜索,然后去两边(向后)我找到的值和索引号,返回正确的答案,我的问题是:

1. 这是最有效的方式吗？
2. 在最坏的情况下,它不会是O(n)吗？(当数组填充一个数字时) -

如果是这样 - 那我为什么要进行二分搜索呢？

人们通常会问这个问题的反面(三元搜索是否优于二元搜索？).

我真的认为情况更糟(不是在O(log n)的复杂性方面).我真的不善于数学,只是纯粹的直觉.

如果我们采用大小为n的数组并使用二进制搜索,在第一次比较之后我们有n/2问题大小,并且在第二次比较之后我们有n/4的问题大小.

通过三元搜索,第一个循环运行已经进行了2次比较!我们的问题大小为n/3.

我是对的还是我错过了什么？在我阅读的所有内容中,人们通常会考虑到三元搜索的第一个循环运行是1比较,我认为这是错误的.