[시간복잡도] 별찍기 문제의 시간복잡도가 O(N^2)인 이유에 대하여
알고리즘을 공부할 때마다 중요하다고 하는 것이 시간복잡도이다. 대충 이해한 것 같다고 생각해도, 막상 복잡도 계산해보라고 하면 못한다. 오늘은 어떻게든 시간복잡도를 파악해보려고 한다. 이해가 안되니 암기라도 해야지 하고 여러 문제를 들여다 보던 중 구현하기는 엄청 쉬운데 시간복잡도 계산은 이해가 되지 않는 문제를 마주쳤다. 바로 N개의 줄에 별을 찍어 출력하는 별찍기 문제.// 입력 예제5// 출력 예제***************// 구현 예제function makestars(n) { for (let i = 1; i 지금까지 이해한 바로는 반복문을 한 번 쓰면 O(N), 두 번쓰면 O(N^2) 이런 식이었기 때문에, 코드만 놓고 보면 별찍기는 O(N^2)이 맞지만(for 안에 repeat으로 이중 반..
Development/Algorithm
2024. 7. 16. 15:33
