자료구조 hw3

12월 27일까지 하는 숙제

문제

1. 두 개의 정렬된 배열을 하나로 합치는 클라이언트 함수나 SortedType
클래스의 멤버 함수를 쓰세요. (두 개중 하나만 코드를 쓰면 됨)
void MergeLists(SortedType list1, SortedType list2, SortedType&
result);
void SortedType::MergeLists(SortedType list2, SortedType&
result)
2. 위 함수의 complexity를 Big(O)로 쓰세요.
3. 데이터 개수 = N일 때, 알고리즘1은 N*N*N 수행 스텝이 걸리고 , 알고
리즘 2는 3*N + 1000 스텝이 걸린다.
① Big O로 각각의 complexity를 쓰세요.
② 어느 알고리즘이 더 효율적인 가요?
③ 비효율적인 알고리즘이 더 효율적인 알고리즘보다 빨리 끝나는 경우도 있
을 수 있을까요?

답
1.
void SortedType::MergeLists(SortedType list2, SortedType& result)
{
        if(list2.LengthIs()==0){
                for(int i=0; i<length; i++)
                        result.info[i] = info[i];
                return ;
        }
        if(length ==0){
                for(int i=0; i<list2.LengthIs();i++)
                        result.info[i] = info[i];
                return ;
        }
        int i=0;
        while((list2.LengthIs() != 0) &&length!=0){

                if(info[0]>list2.info[0]){
                        result.info[i]=list2.info[0];
                        list2.DeleteItem(list2.info[0]);
                        i++;
                        continue;
                }
                else if(info[0]<list2.info[0])
                        result.info[i]=info[0];
                else{
                        result.info[i] = list2.info[0];
                        list2.DeleteItem(list2.info[0]);
                        i++;
                        result.info[i] = info[0];
                }

                i++;
                DeleteItem(info[0]);
        }
        if(list2.LengthIs() == 0){
                for(int j=0;  j<length; j++){
                        result[i] = info[j];
                        i++;
                }
        }else if(length==0){
                for(int j=0; j<list2.LengthIs();j++){
                        result[i]=info[j];
                        i++;
                }
        }
}
2. 두개의 리스트에 들어가있는 원소만큼이므로 O(n)
3.
1)
알고리즘 1 : O(n^3)
알고리즘 2 : O(n)
2)전체적으로 보았을 때에는 알고리즘 2
3)네
위의 경우 n이 11보다 작을 때에는 알고리즘 1이 알고리즘2보다 빨리 끝납니다.
n^3<3*n+1000 을 사용하여 알아볼 수 있습니다.