11/22 TIL

알고리즘... 알고싶음...

시간표대로 공부를 하고 있는데 오늘 시간표에는 알고리즘이 있었다.
전날에 튜터님이 어려울 거라고 하셨는데 진짜 수업 들으면서 물음표 백만개 뜨면서 좌절. 이거 정말 할 수 있나, 개발자 가능한 부분인가? 고민하게 만든 너...
오늘 제일 어려워서 저번 팀 같은 조였던 정민님 붙잡고 물어 본 시간 복잡도를 TIL로 남긴다.

---

• 시간 복잡도
  시간 복잡도란 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말함.

위의 이미지의 시간 복잡도의 해설(?)

string 은 길이가 변할 수 있는 입력값 이므로 N 이라고 지칭한다

alphabet_occurrence_array = [0] * 26 / 대입연산 1번

첫번째 for 문은 N(string)을 매개변수로 받으므로 N

if 문 / 비교 연산 1번

arr_index = ord(char) - ord('a) / 변환 연산 1번 대입연산 1번

alphabet_occurrence_array[arr_index] += 1 / 산술연산 1번 대입연산 1번

max_occurrence = 0 / 대입연산 1번

max_alphabet_index = 0 / 대입연산 1번

두번째 for 문은 배열의 길이가 이미 정해져 있으므로 상수 26

alphabet_occurrence = alphabet_occurrence_array[index] / 대입연산 1번

if 문 / 비교연산 1번

max_alphabet_index = index / 대입연산 1번

max_occurrence = alphabet_occurrence / 대입연산 1번

을 정리하자면 1 + 5N + 2 + 104 이므로 5N + 107 이다

하지만 연산을 할 때 상수가 끼치는 영향은 미미하므로 상수를 제외하면

N만큼의 시간이 걸리는 시간 복잡도 이다.

---

• for문이 한 번 돌 때 안에 포함된 if문과 연산들이 함께 돌기 때문에 (N*for문 안에 돌아가는 연산자들의 수)로 계산
• for문 끼리는 각각 돌아가 중첩되지 않기 때문에 합으로 계산

아직 정확히 다 내 것이 된 느낌은 없지만 위의 식이 중요하다고 생각해서 적어 둔다.
나중에 헷갈릴 때 저것만 읽어도 이해가 되길 바라며...