使代码具有较低的复杂性 [英] Make a code have less Complexity

问题描述

直接从我的上一个问题和我对@Andreas Gieriet的感谢我在C中创建了一个程序，它执行以下程序。



给出一个带有元素的动态数组我们想要制作一个程序，这样我们就可以找到数组中元素的最低总和。



所以如果我们有这些元素： 5 6 1 4 9 3 1 2



程序如下图所示。



http://prntscr.com/60l705 [ ^ ]





最后我们想要最小化重量值。在那种情况下 13 。



我创建了代码，但我想知道程序的复杂性是O（n ^ 3）即使在O（N）中，也有办法将其减少到O（n ^ 2）。

Coming straight from my last question and my thanks to @Andreas Gieriet I create a program in C that make the following procedure.

Giving a dynamic array with elemnts we want to make a procedure so we can find the lowest sum of the elements in the array.

So if we have that elements: 5 6 1 4 9 3 1 2

the procedure will be the following diagram.

http://prntscr.com/60l705[^]


And in the end we want the minimun of the weight values. In that case 13.

I created the code but i was wondering as the Complexity of the program is O(n^3) if there is any way to reduce it to O(n^2) even in O(N).

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>


int sum_array(int* array, int cnt)
{
    int res = 0;
    int i;
    for ( i = 0; i < cnt ; ++i)
        res += array[i];
    return res;
}

int main()
{
    FILE* input = fopen("share.in","r");

    int N = 0;
    fscanf(input,"%d",&N);

    int *array = (int*)malloc(N * sizeof(int));

    for (int i = 0; i < N; i++)
        fscanf(input,"%d",&array[i]);

    fclose(input);

    int Min = 0;
    int bestA = 0, bestB = 0, bestMin = INT_MAX;
    int A, B;
    int i;
    for ( A = 0; A < N - 2; ++A)
    {
        for ( B = A + 1; B < N - 1; ++B)
        {
            int ProfitA = sum_array(array, A + 1);
            int ProfitB = sum_array(array + A + 1, B - A );
            int ProfitC = sum_array(array + B + 1, N - 1 - B );

            //here the values are "current" - valid
            Min = (ProfitA > ProfitB) ? ProfitA : ProfitB;
            Min = (ProfitC > Min) ? ProfitC : Min;

            if( Min < bestMin )
                bestA = A, bestB = B, bestMin = Min;

        }
    }
    printf("%d\n", bestMin);
    free(array);
    return 0;
}

首先想一下使用贪婪算法：

First think using Greedy Algorithm:

int idx0 = 0;
int idx1 = 1;
int idx2 = N-1;

int sum0 = arr[0];
int sum1 = arr[1];
int sum2 = arr[N - 1];

int max = (sum0 > sum1) ? sum0 : sum1;
    max = (sum2 > Max) ? sum2 : Max;

for (i=0; i < N - 1; i++){
    sum += arr[i];
}


while ((idx1 + 1) < idx2) {
    const int left = (sum0 + arr[idx1]);
    const int right = (sum2 + arr[idx2-1]);

    if (left <= right && left <= max) {
        sum0 = left;
        sum1 -= arr[idx1++];
        max = (sum1 > sum2) ? sum1 : sum2; //left cannot be greater
    } else if (right < left && right <= max) {
        sum2 = right;
        sum1 -= arr[--idx2];
        max = (sum1 > sum2) ? sum1 : sum2; //right cannot be greater
    } else break;

    //something like return make_pair(idx[1],idx[2]);
    //and what I return? I return the value I want? The minimun one?

}

那是我的问题，如果有人有任何想法发布答案！

That is my question, if anyone has any idea post an answer!

推荐答案

这是我的方法的代码：

Here is the code of my approach:

int max(int A, int B, int C)
{
    return Math.Max(A, Math.Max(B,C));
}

void Main()
{
    var e = new byte[] {5,6,1,4,9,3,1,2};
    var i=0;
    var j = e.Length-1;
    int A = e[i];
    int C = e[j];
    int B = 0;
    for(int x = i+1 ; x < j; x++) B+=e[x];
    var mp = int.MaxValue;
    var m = max(A,B,C);
    Console.WriteLine("A={0} B={1} C={2}", A, B, C);
    while(m < mp)
    {
        int AL = A+e[i+1];
        int CR = C+e[j-1];
        int BL = B-e[i+1];
        int BR = B-e[j-1];
        if(max(AL,BL,C) < max(A,BR,CR) )
        {
            A=AL;
            B=BL;
            i++;
        }
        else
        {
            C=CR;
            B=BR;
            j--;
        }
        mp = m;
        m = max(A,B,C);
        Console.WriteLine("A={0} B={1} C={2}  MAX={3}", A, B, C, m);
    }
    Console.WriteLine(mp);
}

是的，它是C＃，但很容易在C / C ++中进行描述，因为它没有使用任何特定于.NET的内容。根据您提供的样本输入，它将以6个步骤结束：

Yes, it is C#, but quite easy to trasscribe it in C/C++, as it is not using any .NET specific. With the sample input you have given, it is terminating in 6 steps:

A=5 B=24 C=2
A=11 B=18 C=2  MAX=18
A=11 B=17 C=3  MAX=17
A=11 B=14 C=6  MAX=14
A=12 B=13 C=6  MAX=13
A=12 B=4 C=15  MAX=15
13

点击此处： https://dotnetfiddle.net/LC92ZU [ ^ ]



C中的相同内容:(

Check here: https://dotnetfiddle.net/LC92ZU[^]

Same thing in C :(

#include <stdio.h>
#include <limits.h>
#define max(A,B,C) A > (B > C ? B : C) ? A : (B > C ? B : C)
#define N 10

int main()
{
    int e[N] = {1, 1, 8, 1, 1, 3, 4, 9, 5, 2 };
    int i=0;
    int j = N-1;
    int A = e[i];
    int C = e[j];
    int B = 0;
    int x, AL, CR, BL, BR, m, mp = INT_MAX, L, R;
    for(x = i+1 ; x < j; x++) B+=e[x];
    m = max(A,B,C);
    printf("A=%d B=%d C=%d\n", A, B, C);
    while(m < mp)
    {
        AL = A+e[i+1];
        CR = C+e[j-1];
        BL = B-e[i+1];
        BR = B-e[j-1];
        L = max(AL,BL,C);
        R = max(A,BR,CR);
        if(L<R)
        {
            A=AL;
            B=BL;
            i++;
        }
        else
        {
            C=CR;
            B=BR;
            j--;
        }
        mp = m;
        m = max(A,B,C);
        printf("A=%d B=%d C=%d MAX=%d\n", A, B, C, m);
    }
    printf("%d", mp);
    return 0;
}

在线： http://ideone.com/v1NFTw [ ^ ]

这篇关于使代码具有较低的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！