알고리즘 | 최악 시간 복잡도 (Big O) | 최선 시간 복잡도 (Big Ω) | 평균 시간 복잡도 |
---|---|---|---|
선형 정렬 | O(n) | Ω(n) | O(n) |
버블 정렬 | O(n^2) | Ω(n) | O(n^2) |
선택 정렬 | O(n^2) | Ω(n^2) | O(n^2) |
병합 정렬 | O(n log n) | Ω(n log n) | O(n log n) |
삽입 정렬 | O(n^2) | Ω(n) | O(n^2) |
퀵 정렬 | O(n^2) | Ω(n log n) | O(n log n) |
재귀는 문제를 더 작은 문제로 분할하여 해결하는 데 유용
높이를 입력 받아 중첩 루프를 통해 피라미드를 출력해주는 draw 함수를 정의
#include <cs50.h>
#include <stdio.h>
void draw(int h);
int main(void)
{
int height = get_int("Height: ");
draw(height);
}
void draw(int h)
{
// 높이가 0이라면 (그릴 필요가 없다면)
if (h == 0)
{
return;
}
// 높이가 h-1인 피라미드 그리기
draw(h - 1);
// 피라미드에서 폭이 h인 한 층 그리기
for (int i = 0; i < h; i++)
{
printf("#");
}
printf("\\n");
}