[alice] Big-O, 문제풀이

효율적인 프로그램이란?

 

시간복잡도 : 알고리즘에 사용되는 총 연산횟수

공간복잡도 : 알고리즘에 사용되는 메모리공간의 총량

 

※ 입력변수의 크기 : N -> 코드의 시간복잡도 = f(N)

Big-O : 시간복잡도 함수의 가장 높은 차수

 

 

<계산법칙>

반복문 : 한번 중첩마다 O(N)

list 다돌면 : O(N)

set : O(N)

sort() : O(NlogN)

매번 절반씩 입력값이 줄어들면 : O(logN)

 

 

 

<배열> - 시간복잡도

 

인덱스를 알 때 : O(1)

인덱스를 모를 때 : O(N)

배열을 전부 순회 : O(N)

자료끝에 추가 : O(1)

자료중간에 추가 : O(N)    <- insert (나머지 숫자를 뒤로 밀어줘야 하기 때문에)

 

 

 

<해쉬>

• key에 value를 저장하는 자료구조
• 공간복잡도 : O(N)
• 키 중복x

 

(시간복잡도)

• key 이용해서 value 가져오기, 변경하기 : O(1)
• key 존재확인 : O(1)

 

<SET>

• value(x), key(o) 인 dict

 

 

 

[중복된 수]

 

[코드]

 

 

 

 

[0이동 시키기]

 

[코드]

 

(2번째 코드)

 

[최적코드]

 

 

 

[배열회전]

 

 

[내가 한 코드]

분명 답은 알맞게 나왔는데 오답으로 떳다.

 

[강의 코드]

똑같은 코드인데 정답으로 떳다.

인덱싱이 조금 다르긴한데 이게 어떻게 문제가 되는건지 잘 모르겠다..

 

 

 

[아나그램]

 

[코드]