算法分析:我是否正确分析了这些算法？如何解决这些问题

Question

1)

  x = 25;
    for (int i = 0; i < myArray.length; i++)
    {
        if (myArray[i] == x)
            System.out.println("found!");
    }

我认为这个是O(n).

2)

for (int r = 0; r < 10000; r++)
    for (int c = 0; c < 10000; c++)
        if (c % r == 0)
            System.out.println("blah!");

我认为这个是O(1),因为对于任何输入n,它将运行10000*10000次.不确定这是否正确.

3)

a = 0
for (int i = 0; i < k; i++)
{
    for (int j = 0; j < i; j++)
        a++;
}

我认为这个是O(i*k).我真的不知道如何处理这样的问题,其中内部循环受外部循环中递增的变量的影响.这里的一些重要见解将非常感激.外循环运行k次,内循环运行1 + 2 + 3 + ... + k次.因此,该和应为(k/2)*(k + 1),其为k ^ 2的阶数.它实际上是O(k ^ 3)吗？这似乎太大了.再次,不知道如何处理这个问题.

4)

int key = 0;    //key may be any value
int first = 0;
int last = intArray.length-1;;
int mid = 0;
boolean found = false;

while( (!found) && (first <= last) )
{
    mid = (first + last) / 2;

    if(key == intArray[mid]) 
        found = true;
    if(key < intArray[mid])
        last = mid - 1;
    if(key > intArray[mid]) 
        first = mid + 1;
}

这个,我认为是O(log n).但是,我得出了这个结论,因为我相信它是一个二进制搜索,我从阅读中知道运行时是O(log n).我认为这是因为你为循环的每次迭代将输入大小除以2.但是,我不知道这是正确的推理还是如何处理我没见过的类似算法,并且能够推断它们以更加可验证或正式的方式在对数时间内运行.

5)

int currentMinIndex = 0;

for (int front = 0; front < intArray.length; front++)
{
    currentMinIndex = front;

    for (int i = front; i < intArray.length; i++)
    {
        if (intArray[i] < intArray[currentMinIndex])
        {
            currentMinIndex = i;
        }
    }

    int tmp = intArray[front];
    intArray[front] = intArray[currentMinIndex];
    intArray[currentMinIndex] = tmp;
}

我很困惑这个.外循环运行n次.内部for循环运行n +(n-1)+(n-2)+ ...(n - k)+ 1次？O(n ^ 3)??

Answer 1

或多或少，是的。

1 是正确的 - 看来您正在寻找一个特定的元素，我认为这是一个未排序的集合。如果是这样，最坏的情况是该元素位于列表的最末尾，因此 O(n)。

2 是正确的，虽然有点奇怪。假设r和c是常量并且界限不是变量，其时间复杂度为 O(1)。如果它们是常数，那么是 O(1)，因为没有任何输入。

3 我相信这仍然被认为是 O(n^2) 。会有一些常数因子，例如 k * n^2，去掉常数，就得到 O(n^2)。

4 看起来很像排序集合的二分搜索算法。O(logn) 是正确的。它是对数，因为在每次迭代中，您基本上将要查找的元素可能存在的可能选择数量减半。

5 看起来像冒泡排序，O(n^2)，原因与 3 类似。