oio3215   3년 전

A= {1,2,3,4,1,2,1} 이라고 할때

중복제거를 하는데

A[0]일 때 A[1~6]까지 검사하고

A[1]일땐 A[2~6]만 검사하고

이렇게 자기보다 한자리수 높게 중복검사를 하면

어쨋든 for문이 두개긴한데

이렇게 해도 O(N^2)의 시간복잡도를 갖게 되는건가요?

kesakiyo   3년 전

그렇게 했을때 for문의 횟수는 (N - 1) + (N - 2) + (N - 3) + ... + 1 이 됩니다.

이를 수식으로 표현하면 N * (N - 1) / 2 이 됩니다.

Big-O 표기법에서는 계수를 제외한 최고차항을 확인하면 되므로 O(N^2)이 됩니다.

댓글을 작성하려면 로그인해야 합니다.