문제

• nxn 배열 A의 원소들 중 특정 원소 x를 찾는 알고리즘 -> findMatrix 작성
• 알고리즘 findMatrix는 (1) A의 행들을 반복하며, x를 찾거나 (2) A의 모든 행들에 대한 탐색을 마칠 때까지, 각 행에 대해 알고리즘 findRow를 호출한다

Alg findRow(A,x)
	input array A of n elements, element x
    output the index i such that x = A[i] or -1 if no element of A is equal to x
    
1. i <- 0
2. while(i < n)
	if(A[i] = x)
    	return i
    else
    	i <- i+1
3. return -1

문제 A

위의 의도한 바와 일치하도록 알고리즘 findMatrix를 의사코드로 작성하라

Alg findMatrix(A,x)
	input array of n elements, element x
    output the location of x or a failure meassage if no element of A is equal to x
    
1. r <- 0
2. while(r<n)
	i <- findRow(A[r],x)
    if(i>=0)
    	write("found at", r, i)
        return
    else
    	r <- r+1
3. write("not found")
4. return

문제 B

findMatrix의 최악실행시간을 n에 관해 구해라

최악의 경우 찾는 원소 x가 행렬A의 마지막 원소일 수 있다.
이럴 경우 각 행 마다 findRow 알고리즘을 n번 호출
따라서 총 $n*n$회의 작업을 수행하게 되며 이는 $O(n^2)$ 실행시간이다.

문제 C

이는 선형시간 알고리즘인가? 왜 그런지 또는 왜 아닌지 설명하라

아니다. $n^2$는 2차시간(quadratic-time)이다.
즉, 실행시간이 입력 크기에 제곱비례한다.

선형시간이 되려면 입력크기에 정비례해야 할 것이다.