시간복잡도 구하는 문제 및 코드 작성 foundation of algorithmn

소개

시간복잡도 구하는 문제 및 코드 작성 foundation of algorithmn

에 대한 문제풀이
foundation of algorithmn

목차

6. Write an algorithm that finds the both the smallest and largest numbers in a list of n numbers. Try to finds a method that does at most 1.5n comparisons if array items.
알고리즘 설명
코드)
실행결과)
14. There are two algoritms calles Alg1 and Alg2 for a problem of size n, Alg1 runs in microseconds and Alg2 runs in microseconds. Alg1 can be implemented using 4 hours of programmer time and needs 2 minutes of CPU time. On the other hand, Alg2 requires 15 hours of programmer time and 6 minutes of CPU time. If programmers are paid 20 dollars per hour and CPU time costs 50 dollars per minute, how many times must a problem instance of size 500 be solved using Alg2 in order to justify its development cost?
15. Show directly that . That is use the definitions of O and to show that is in both and .
26. Consider the following algorithm:
27. Consider the following algorithm:
28. What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, for some positive integer k.
29. Give an algorithm for the following problem and determine its time complexity. Given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is maximized. You may assume that n is a multiple of 2.
30. What is the time complexity T(n) if the nested loops below? For simplicity, you may assume that n is a power of 2. That is, for some positive integer k.
35. Give an algorithm for the following problem. Given a list of n distinct positive integers, partition the list into two sublists, each of size n/2, such that the difference between the sums of the integers in the two sublists is minimized. Determine the time complexity of your algorithm. You may assume that n is a multiple of 2.

본문내용

알고리즘 설명
1. n개의 숫자로 이루어진 크기n의 배열이 있으면 2개씩 짝지어서 순차적으로 대소 비교를한다.
2.새로생성한 크기가 n인 배열에 앞부분은 비교연산결과 큰값들을 모아놓고
뒷부분에는 연산결과 작은값 들끼리 모아놓는다.
(뒷부분이라 함은 중간부분이 뒷부분 시작지점이다.)
3. 앞부분의 큰값들을 모아논 부분에서는 어느게 더큰지 비교하고
3-2 뒷부분의 작은값들을 모아논 부분에서는 어느게 작은지 비교한다.
4. 비교된 값들을 앞쪽엔 다시 큰값들 뒤쪽엔 작은값들을 차례로 넣는다.
5. 이과정을 반복하다보면 최종적으로 2개의 수만 남게된다.
6. 이때 첫 번째 값이 최대값 두 번째 값이 최소값으로 각각 결정된다.
예를들면 다음과 같이 된다.

코드)
※ 크기가 유동적인 배열 대신 크기를 8로 고정하고 프로그램을 구성하였다.

참고자료

· 없음