계명대 컴퓨터 알고리즘 과제 입니다.

소개글

계명대 컴퓨터 알고리즘 과목의 과제 입니다.
1차,2차,3차 과제와 테스트 소스 있습니다.
테스트 소스는 C#으로 작성되어 있습니다.

목차

1차,2차,3차 과제와 테스트 소스

본문내용

① 세 알고리즘의 시간복잡도를 비교하시오.

MergeSort1 : mergesort() 연산은 배열 s[]를 이등분으로 분할하여 부분 배열을 만들고 각 부분 배열에 대해서 mergesort()를 순환 호출하여 이등분으로 분할하는 작업을 반복하는데, 부분 배열의 원소가 한 개가 될 때까지 분할 작업을 계속한다. 분할 작업이 끝나면 merge() 연산을 이용하여 부분 배열을 정렬하면서 병합하는 작업을 반복하여 하나의 전체 배열을 완성한다. n개의 원소를 분할하기 위해서 log2n번의 단계를 수행하고, 부분집합의 원소를 비교하면서 병합하는 단계에서 최대 n번의 비교 연산을 수행하게 되므로 시간 복잡도는 O(nlog2n)이 된다. 하지만 단점으로는 최악의 경우에도 n개의 원소를 정렬하는데 nlog2n에 비례하는 시간이 걸린다는 것이다. 그러므로 일반 적인 합병정렬은 들어온 데이터가 최악이든 아니든 상관없이 항상 nlog2n에 비례하는 시간이 걸리게 된다.
또한 합병 정렬은 combine 하는 과정에서 모든 작업이 거의 다 이루어진다.

MergeSort2 : MergeSort1보다 공간 복잡도를 줄임으로써 시간 복잡도가 약간 증가 하였다. 시간복잡도가 O(nlog2n)이다.

참고 자료

없음

압축파일 내 파일목록

두번째과제/item1.txt
두번째과제/item2.txt
두번째과제/item3.txt
두번째과제/과제물2.pdf
두번째과제/문제 설명컴퓨터알고리즘 과제물2.hwp
두번째과제/KnapsackProblem/KnapsackProblem.sln
두번째과제/KnapsackProblem/KnapsackProblem.suo
두번째과제/KnapsackProblem/KnapsackProblem/KnapsackProblem.csproj
두번째과제/KnapsackProblem/KnapsackProblem/Program.cs
두번째과제/KnapsackProblem/KnapsackProblem/Program.cs.bak
두번째과제/KnapsackProblem/KnapsackProblem/bin/Debug/item1.txt
두번째과제/KnapsackProblem/KnapsackProblem/bin/Debug/item2.txt
두번째과제/KnapsackProblem/KnapsackProblem/bin/Debug/item3.txt
두번째과제/KnapsackProblem/KnapsackProblem/bin/Debug/KnapsackProblem.exe
두번째과제/KnapsackProblem/KnapsackProblem/bin/Debug/KnapsackProblem.pdb
두번째과제/KnapsackProblem/KnapsackProblem/bin/Debug/KnapsackProblem.vshost.exe
두번째과제/KnapsackProblem/KnapsackProblem/obj/KnapsackProblem.csproj.FileListAbsolute.txt
두번째과제/KnapsackProblem/KnapsackProblem/obj/Debug/KnapsackProblem.exe
두번째과제/KnapsackProblem/KnapsackProblem/obj/Debug/KnapsackProblem.pdb
두번째과제/KnapsackProblem/KnapsackProblem/obj/Debug/TempPE/
두번째과제/KnapsackProblem/KnapsackProblem/Properties/AssemblyInfo.cs
세번째과제/branch.cpp
세번째과제/data.txt
세번째과제/data1.txt
세번째과제/TravelingSalesmanProblem.hwp
세번째과제/과제물3.pdf
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem.sln
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem.suo
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/Program.cs
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/TravelingSalesmanProblem.csproj
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/bin/Debug/data.txt
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/bin/Debug/data1.txt
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/bin/Debug/TravelingSalesmanProblem.exe
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/bin/Debug/TravelingSalesmanProblem.pdb
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/bin/Debug/TravelingSalesmanProblem.vshost.exe
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/obj/TravelingSalesmanProblem.csproj.FileListAbsolute.txt
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/obj/Debug/TempPE/
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/obj/Debug/TravelingSalesmanProblem.exe
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/obj/Debug/TravelingSalesmanProblem.pdb
세번째과제/TravelingSalesmanProblem/TravelingSalesmanProblem/Properties/AssemblyInfo.cs
첫번째과제/과제물1.pdf
첫번째과제/프로그래밍 과제물 #1.hwp
첫번째과제/DivideAndConquer/DivideAndConquer.sln
첫번째과제/DivideAndConquer/DivideAndConquer.suo
첫번째과제/DivideAndConquer/DivideAndConquer/DivideAndConquer.csproj
첫번째과제/DivideAndConquer/DivideAndConquer/Program.cs
첫번째과제/DivideAndConquer/DivideAndConquer/Program.cs.bak
첫번째과제/DivideAndConquer/DivideAndConquer/bin/Debug/DivideAndConquer.exe
첫번째과제/DivideAndConquer/DivideAndConquer/bin/Debug/DivideAndConquer.pdb
첫번째과제/DivideAndConquer/DivideAndConquer/bin/Debug/DivideAndConquer.vshost.exe
첫번째과제/DivideAndConquer/DivideAndConquer/obj/DivideAndConquer.csproj.FileListAbsolute.txt
첫번째과제/DivideAndConquer/DivideAndConquer/obj/Debug/DivideAndConquer.exe
첫번째과제/DivideAndConquer/DivideAndConquer/obj/Debug/DivideAndConquer.pdb
첫번째과제/DivideAndConquer/DivideAndConquer/obj/Debug/TempPE/
첫번째과제/DivideAndConquer/DivideAndConquer/Properties/AssemblyInfo.cs

전체 목록 보기