使代码具有较低的复杂性

本文介绍了使代码具有较低的复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

直接从我的上一个问题和我对@Andreas Gieriet的感谢我在C中创建了一个程序，它执行以下程序。 给出一个带有元素的动态数组我们想要制作一个程序，这样我们就可以找到数组中元素的最低总和。 所以如果我们有这些元素： 5 6 1 4 9 3 1 2 程序如下图所示。 prntscr/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. prntscr/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

点击此处： dotnetfiddle/LC92ZU [ ^ ] C中的相同内容:(

Check here: dotnetfiddle/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; }

在线： ideone/v1NFTw [ ^ ]