데이터 구조 작업 - 시간 복잡 도 를 어떻게 구 합 니까?

1.For each of the following six program fragments:Give an analysis of the running time(Big-Oh will do)

(1) sum = 0;
        for (i=0;i<N;i++)
           sum++;

답: O (N)

(2) sum = 0;
        for (i=0;i<N;i++)
            for(j=0;j<N;j++)
                sum++;

답: O (N2)

(3) sum = 0;
        for (i=0;i<N;i++)
            for(j=0;j<N*N;j++)
                sum++;

답: O (N3)

(4) sum = 0;
        for (i=0;i<N;i++)
            for(j=0;j<i;j++)
                sum++;

답: O (N2)

(5) sum = 0;
        for (i=0;i<N;i++)
            for(j=0;j<i*i;j++)
                for(k=0;k<j;k++)
                sum++;

답: O (N5)

(6) sum = 0;
        for (i=0;i<N;i++)
            for(j=0;j<i*i;j++)
                if(j%i == 0)
                  for(k=0;k<j;k++)
                       sum++;

답: O (N4)
2.Description: Given a group of N numbers, determine the kth largest, where N > k . Solution 1: (1) read N numbers into an array, (2) sort the array in decreasing order by some simple algorithm (such as bubblesort), (3) return the element in position k. Solution 2: (1) read the first k elements into an array and sort them in decreasing order, (2) each remaining element is read one by one, (2.1) If it is smaller than the kth element in the array, it is ignored; (2.2) Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. (3) the element in the kth position is returned as the answer Which solution is better when (1) N ~ k (2) N » k ?
답: (1) 의 경우 Solution 1 과 Solution 2 가 모두 가능 합 니 다.(2) 의 경우 Solution 2 가 Solution 1 보다 낫다.그러나 N 이 매우 클 때 (예 를 들 어 백만, 천만 급) Solution 1 과 Solution 2 는 모두 장시간 운행 해 야 결 과 를 얻 을 수 있다.다시 말하자면 Solution 2 는 Solution 1 에 대한 개선 이지 만 아직 부족 하고 둘 다 좋 은 결과 가 아니다.