1. 주제 설명
1000개의 정수를 저장하는 배열 a[1000]이 있습니다. 배열에서 합이 M인 숫자 쌍을 모두 찾으세요. 예를 들어 배열이 -1,2,4,6,5,3,4,2,9,0,8,3이면 합이 8인 숫자 쌍은 (-1,9), (2, 6), (4,4), (5,3), (5,3), (0,8).
2. 가장 일반적인 알고리즘
환원 불가능한 복잡성의 경우 이 문제에 대한 가장 간단한 알고리즘은 다음과 같습니다.
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> 결과 = 새로운 List<int[]>();
for (int i = 0; i < arr.Length; i++)
{
int ExpectNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] == 기대Num)
{
result.Add(new int[]{arr[i], ExpectNum});
}
}
}
결과 반환;
}
2단계 루프를 사용하여 합계가 고정된 수 sumTotal인 모든 쌍을 찾고 찾은 쌍을 목록에 저장합니다. 그러나 이 알고리즘의 복잡성은 약간 높으며 실제로 순회 중에 일부 반복 작업을 수행합니다.
1) 후속 루프에서는 이전에 쌍을 이룬 시퀀스를 처리할 필요가 없습니다.
2) 합계가 sumTotal인 숫자를 검색할 때 상호 사용할 수 있는 프로세스가 있어야 합니다.
이 두 가지 점을 바탕으로 이 알고리즘을 개선하고 재귀를 사용하여 작동하기 위해 01 배낭이나 동적 프로그래밍 아이디어(아마 부적절할 수도 있지만 나는 이 두 가지 아이디어에 대해 피상적으로 이해하고 있음)를 인용할 수 있습니다.
2. 재귀 알고리즘 사용
재귀 알고리즘을 사용한 코드는 다음과 같습니다.
private static List<int[]> UseRecursion(int[] arr, int 길이, int sumTotal)
{
List<int[]> 결과 = 새로운 List<int[]>();
int[] nextArr = 새로운 int[length];
int nextLength = 0;
int ExpectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < 길이; i++)
{
if (arr[i] == 기대Num)
{
int CircleCount = arr[0] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for(int j = 0; j < CircleCount; j++)
{
result.Add(new int[] { arr[0], ExpectNum });
}
findEndNumCount++;
}
그렇지 않으면 (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] { ExpectNum, arr[0] });
}
findStartNumCount++;
}
또 다른
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach(nextResult의 int[] 항목)
{
결과.추가(항목);
}
}
결과 반환;
}
각 재귀 후에 일치 여부가 확인되지 않은 모든 숫자는 다음 재귀에서 처리하기 위해 새로운 배열로 구성되지만 이는 엄청난 양의 공간을 낭비하며 특히 배열이 클 경우 많은 메모리를 소비하게 됩니다. . 매번 재귀적으로 새로운 배열을 생성하지 않으려면 원래 배열에서 처리하고 배열에서 일치하는 숫자를 제거한 후 다음 숫자를 앞으로 이동하여 교체하면 됩니다.
3. 배열 동적 변경 알고리즘
이 알고리즘의 코드는 다음과 같습니다.
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> 결과 = 새로운 List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
while(startIndex < endIndex)
{
int ExpectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
if (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
if (arr[i] == 기대Num)
{
int CircleCount = arr[startIndex] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for (int iStart = 0; iStart < CircleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
나--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] { ExpectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
나--;
}
}
시작인덱스++;
}
결과 반환;
}
이 알고리즘은 원래 배열의 데이터를 파괴합니다.
4. 세 가지 알고리즘의 시간 비교
후자의 두 알고리즘의 원래 의도는 시간 복잡도를 줄이는 것이지만 특정 테스트에서는 첫 번째 알고리즘보다 그다지 좋지 않습니다. 특히 재귀 알고리즘은 첫 번째 알고리즘보다 훨씬 오래 걸립니다. 어쩌면 내 생각에 근본적인 문제가 있을 수도 있고, 아니면 이 예가 너무 단순해서 모바일 데이터가 차지하는 시간이 명백해질 수도 있습니다.
나는 알고리즘에 대해 많은 연구를 해본 적이 없습니다. 전문가들이 나에게 더 완벽한 해결책이 있어야 한다고 믿습니다.
5. 모든 코드
정적 무효 Main(string[] args)
{
const int NUM_COUNT = 8000;
const int MIN_NUM = -4;
const int MAX_NUM = 12;
const int TOTAL = 8;
int[] arr = 생성Array(NUM_COUNT, MIN_NUM, MAX_NUM);
//Console.WriteLine("생성된 숫자는 다음과 같습니다.n------------------------- ---- -");
//PrintNumArray(arr);
//일반적인 방법
TimeSpan NormalTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
스톱워치 NormalStw = 새로운 스톱워치();
NormalStw.Start();
List<int[]> resultUseNormalWay = UseNormalWay(arr, TOTAL);
double NormalCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(normalTimeStart).TotalMilliseconds;
NormalStw.Stop();
double NormalRealTime = NormalStw.Elapsed.TotalMilliseconds;
// 일반 결과를 인쇄합니다.
//Console.WriteLine("일반적인 방법을 사용한 결과 숫자 쌍은 다음과 같습니다:n-------------------------------- --");
//PrintNumPairs(resultUseNormalWay);
// 재귀 방식
TimeSpan recuTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
스톱워치 recuStw = new 스톱워치();
recuStw.Start();
List<int[]> resultUseRecursionWay = UseRecursion(arr, arr.Length, TOTAL);
double recuCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(recuTimeStart).TotalMilliseconds;
recuStw.Stop();
double recuRealTime = recuStw.Elapsed.TotalMilliseconds;
// 재귀 결과를 인쇄합니다.
//Console.WriteLine("재귀환 방식을 사용한 결과 숫자 쌍은 다음과 같습니다:n-------------------------------- --");
//PrintNumPairs(resultUseRecursionWay);
// 고급 방법
TimeSpan advTimeStart = Process.GetCurrentProcess().TotalProcessorTime;
스톱워치 advStw = 새로운 스톱워치();
advStw.Start();
List<int[]> resultUseAdvancedWay = UseAdvancedWay(arr, TOTAL);
double advCupTime = Process.GetCurrentProcess().TotalProcessorTime.Subtract(advTimeStart).TotalMilliseconds;
advStw.Stop();
double advRealTime = advStw.Elapsed.TotalMilliseconds;
// 고급 결과 인쇄
//Console.WriteLine("고급 방식을 사용한 결과 번호 쌍은 다음과 같습니다.n-------------------------------- --");
//PrintNumPairs(resultUseAdvancedWay);
Console.WriteLine("n================================n사용된 시간:n---- ---------------------");
Console.WriteLine(String.Format("Normal : 개수 - {0} CPU 시간 - {1} 실시간 - {2}", resultUseNormalWay.Count, NormalCupTime, NormalRealTime));
Console.WriteLine(String.Format("재귀: 개수 - {0} CPU 시간 - {1} 실시간 - {2}", resultUseRecursionWay.Count, recuCupTime, recuRealTime));
Console.WriteLine(String.Format("고급: 개수 - {0} CPU 시간 - {1} 실시간 - {2}", resultUseAdvancedWay.Count, advCupTime, advRealTime));
Console.Read();
}
개인 정적 int[] 생성Array(int numCount, int minValue, int maxValue)
{
int[] arr = 새로운 int[numCount];
Random rdm = new Random((int)DateTime.Now.Ticks);
for (int i = 0; i < arr.Length; i++)
{
arr[i] = rdm.Next(minValue, maxValue);
}
반환 도착;
}
개인 정적 무효 PrintNumArray(int[] arr)
{
for (int i = 0; i < arr.Length; i++)
{
if (i > 0 && i % 20 == 0)
{
Console.Write("n");
}
Console.Write(String.Format("{0,2} ", arr[i]));
}
Console.Write("n");
}
개인 정적 무효 PrintNumPairs(List<int[]> numList)
{
for (int i = 0; i < numList.Count; i++)
{
if (i > 0 && i % 10 == 0)
{
Console.Write("n");
}
Console.Write(string.Format("({0,2},{1,2}) ", numList[i][0], numList[i][1]));
}
Console.Write("n");
}
private static List<int[]> UseNormalWay(int[] arr, int sumTotal)
{
List<int[]> 결과 = 새로운 List<int[]>();
for (int i = 0; i < arr.Length; i++)
{
int ExpectNum = sumTotal - arr[i];
for (int j = i + 1; j < arr.Length; j++)
{
if (arr[j] == 기대Num)
{
result.Add(new int[]{arr[i], ExpectNum});
}
}
}
결과 반환;
}
private static List<int[]> UseRecursion(int[] arr, int 길이, int sumTotal)
{
List<int[]> 결과 = 새로운 List<int[]>();
int[] nextArr = 새로운 int[length];
int nextLength = 0;
int ExpectNum = sumTotal - arr[0];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = 1; i < 길이; i++)
{
if (arr[i] == 기대Num)
{
int CircleCount = arr[0] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for(int j = 0; j < CircleCount; j++)
{
result.Add(new int[] { arr[0], ExpectNum });
}
findEndNumCount++;
}
그렇지 않으면 (arr[i] == arr[0])
{
for (int j = 0; j < findEndNumCount; j++)
{
result.Add(new int[] { ExpectNum, arr[0] });
}
findStartNumCount++;
}
또 다른
{
nextArr[nextLength++] = arr[i];
}
}
if (nextLength > 0)
{
List<int[]> nextResult = UseRecursion(nextArr, nextLength, sumTotal);
foreach(nextResult의 int[] 항목)
{
결과.추가(항목);
}
}
결과 반환;
}
private static List<int[]> UseAdvancedWay(int[] arr, int sumTotal)
{
List<int[]> 결과 = 새로운 List<int[]>();
int startIndex = 0, endIndex = arr.Length - 1;
while(startIndex < endIndex)
{
int ExpectNum = sumTotal - arr[startIndex];
int findStartNumCount = 0;
int findEndNumCount = 0;
for (int i = startIndex + 1; i <= endIndex; i++)
{
if (findStartNumCount > 0 || findEndNumCount > 0)
{
arr[i] = arr[i + findStartNumCount + findEndNumCount];
}
if (arr[i] == 기대Num)
{
int CircleCount = arr[startIndex] == ExpectNum ? findEndNumCount : findStartNumCount;
CircleCount += 1;
for (int iStart = 0; iStart < CircleCount; iStart++)
{
result.Add(new int[] { arr[startIndex], arr[i] });
}
findEndNumCount++;
endIndex--;
나--;
}
else if (arr[i] == arr[startIndex] && arr[startIndex] != ExpectNum)
{
for (int iEnd = 0; iEnd < findEndNumCount; iEnd++)
{
result.Add(new int[] { ExpectNum, arr[i] });
}
findStartNumCount++;
endIndex--;
나--;
}
}
시작인덱스++;
}
결과 반환;
}
-