算法的天真code复杂处理所有连续的子序列的清单：N ^ 2或N ^ 3？ [英] Algorithmic complexity of naive code for processing all consecutive subsequences of a list: n^2 or n^3?

问题描述

我学习了测试，发现了这个问题：

我真的不能确定的复杂性，我想它要么为O（n ² ）或为O（n ³ ）和我倾向于为O（n ³ ）。
谁能告诉我它是什么，为什么？

我的想法，这是为O（n ² ）是因为在Ĵ循环， J = 这给出了一个三角形，然后 K 回路从 I + 1 到Ĵ，我认为这是三角形的另一半。

 公共静态INT什么（INT [] ARR）
{
    INT米=改编[0];
    的for（int i = 0; I＆LT; arr.length;我++）
    {
        对于（INT J =; J＆LT; arr.length; J ++）
        {
            INT S =改编[I]
            对于（INT K = 1 + 1; K＆LT; = j的; k ++）
             S + = ARR [K]
            如果（S取代;米）
             米=秒;
        }
    }
    返回米;
}
 

此外，如果你能告诉我是什么呢？

我想它返回除了正整数或数组中的最大整数。
但对于数组像 {99，-3，0，1} 返回 99 ，我认为这是因为它是越野车。如果不是，我不知道它做什么：

  {99，1} =＆GT;返回100
{-1，-2，-3} =＆GT;返回-1
{-1，5，-2} =＆GT;返回5
{99，-3,0，1} =＆GT;返回99 ???
 

解决方案

您可以有条不紊地进行，适马符号，以获得增长的复杂性的顺序：

I'm studying for a test and found this question:

I can't really determine the complexity, I figured it's either O(n²) or O(n³) and I'm leaning towards O(n³).
Can someone tell me what it is and why?

My idea that it's O(n²) is because in the j loop, j = i which gives a triangle shape, and then the k loop goes from i + 1 to j, which I think is the other half of the triangle.

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;
}

Also if you can tell me what it does?

I figured it returns the addition of positive integers or the biggest integer in the array.
But for arrays like {99, -3, 0, 1} it returns 99, which I think is because it's buggy. If not than I have no Idea what it does:

{99, 1} => returns 100
{-1, -2, -3} => return -1
{-1, 5, -2} => returns 5
{99, -3, 0, 1} => returns 99 ???

解决方案

You can proceed methodically, using Sigma Notation, to obtain the order of growth complexity:

这篇关于算法的天真code复杂处理所有连续的子序列的清单：N ^ 2或N ^ 3？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！