★시간복잡도 기초 - 7문제()★

* 백준 요약

→ 백준 24262 - 함수 한 번에 return문 1번 실행, 배열의 indexing은 O(1)

→ 백준 24263 - for문 input() N번 실행, O(N)

→ 백준 23235 - 이미 정렬된 array를 sorting하는 데 필요한 time complexity는 O(1)

→ 백준 24264 - 중첩 for문 $N^2$번 실행, $O(N^2)$

→ 백준 24265 - 중첩 for문 $N^2$번 실행, $O(N^2)$

→ 백준 24266 - 중첩 for문 $N^3$번 실행, $O(N^3)$

→ 백준 24267 - 중첩 for문 $N^3$번 실행, $O(N^3)$

---

★ 24262 알고리즘 수업 - 알고리즘의 수행 시간 1 ★

print(1,0,sep='\n')

 

☀️ 1) 코드1의 수행횟수는 무조건 1이다. n이 어떤 숫자가 들어가든 return문은 무조건 한 번 실행!

☀️ 2) 알고리즘 수행 시간 time complexity는 O(1). A라는 배열의 indexing이므로, index를 이용해서 한 번에 한 개의 위치만 찾기 때문에 traverse 필요 없이 O(1)이 소요된다

---

★ 24263 알고리즘 수업 - 알고리즘의 수행 시간 2 ★

print(input(),1,sep='\n')

 

☀️ for문을 돌릴 때 n의 개수만큼 진행되므로 time complexity는 O(n), 코드1은 입력한 n번만큼 실행된다.

---

★ 23235 The Fastest Sorting Algorithm In The World ★

i = 0
while 1:
    N = list(map(int,input().split()))
    i += 1
    if N[0] == 0:
        break

    print(f'Case {i}: Sorting... done!')

 

☀️ sort() 사용이 아닌, 이미 정렬된 array의 time complexity는 당연히 O(1)!

---

★ 24264 알고리즘 수업 - 알고리즘의 수행 시간 3 ★

print(int(input())**2,2,sep='\n')

---

★ 24265 알고리즘 수업 - 알고리즘의 수행 시간 4 ★

n=int(input())
print(n*(n-1)//2,2,sep='\n')

 

☀️ 중첩 for문은 시간 복잡도 $O(N^2)$

---

★ 24266 알고리즘 수업 - 알고리즘의 수행 시간 5 ★

print(int(input())**3)
print(3)

 

☀️ for문을 세 번 중첩했으므로 $O(N)^3$

---

★ 24267 알고리즘 수업 - 알고리즘의 수행 시간 6 ★

 

n=int(input())
print(n*(n-1)*(n-2)//6)
print(3)

 

☀️ for문 세 번 중첩이므로 시간 복잡도는 $O(N^3)$

 

☀️ 그리고 i가 1부터 n - 2 일 때 그 다음 for문에 i + 1 부터 n - 1, 그 다음 for문에 j + 1 부터 n이 선택되는 것으로 보아, 중복없이 모든 세 개로 이루어진 쌍을 뽑는 경우이므로 nC3의 경우의 수임을 알 수 있다.

---