시간 복잡도

코딩에서 명령어들이 몇 번이나 실행이 되는지를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미한다.

시간 복잡도 표기방법

시간 복잡도를 표기하는 방법중에는 Big-O 표기법이 있다. 실행시간을 n이라고 치면 O(n)이라고 표기하는 방법이다. (차수가 가장 높은 최고차항빼고 다 버린다.)
Big-O 표기법을 다양하게 적을 수 있다.

Big-O 표기법별 대표 알고리즘

• O(1): Operation push and pop on Stack
• O(log n): Binary Tree
• O(n): for loop
• O(n×log n): Quick Sort, Merge Sort, Heap Sort
• O(n2): Double for loop, Insert Sort, Bubble Sort, Selection Sort
• O(2n): Fibonacci Sequence

동적 메모리 할당

입력되는 데이터의 기억공간을 확보 하는 것을 동적 메모리 할당이라고 한다.

사용하는 이유

char test[10];

위 코드에서 test에는 10개의 자료형이 들어갈 수 있다. 하지만 10개를 채우지 못하는 "test"를 넣는다고 하면 공간은 10개가 있지만 4글자 밖에 들어가지 않아 나머지 6칸을 버리게 된는 샘이다. 그러기에 메모리 낭비를 최소화 하기 위해 데이터에 맞게 기억공간을 할당 할 필요가 있다.

동적 메모리 함수

종류 : malloc(), calloc(), realloc(), free()

할당 : malloc(), calloc()
재할당 : realloc()
해제 : free()

malloc() vs calloc()

malloc과 calloc의 가장 큰 차이점은 malloc은 할당 된 메모리를 지우거나 초기화 하지 않는다. 그렇기에 malloc은 쓰레기 값을 포함하고 할당 된 메모리 항목을 변경할 수 없다. 반면 calloc은 할당 된 메모를 0으로 초기화 한다.

ex)

#include <stdio.h>
#include <stdlib.h>
int main() {        
    int *a; 
    int *b;
    a = (int *)malloc(sizeof(int) * 3);
    printf("malloc : %d %d %d\n", a[0], a[1], a[2]);
    b = (int *)calloc(3, sizeof(int));
    printf("calloc : %d %d %d\n", b[0], b[1], b[2]);
    free(a);
    free(b);
}

위에 코드는 malloc과 calloc을 할당만 하고 출력했을 때의 예시이다.
malloc을 사용하여 int형만큼의 크기를 3칸 만들고 바로 출력했다. calloc도 마찬가지.
위에 코드를 실행시켜보면
malloc : -842150451 -842150451 -842150451
calloc : 0 0 0
라는 결과가 나온다.
위에 코드를 보면 알다 시피 calloc은 0으로 초기화하기 때문에 0만 게속 나온다.

linked list & vector

둘의 주요 차이점은 작업에서의 성능 차이이다.

연결 리스트(linked list)의 장점 :

• 자료의 삽입과 삭제가 용이하다.
• 사용 후 기억 장소의 재사용이 가능하다.
• 리스트 내에서 자료의 이동이 필요하지 않다

---

연결 리스트(linked list)의 단점 :

• 포인터의 사용으로 인해 저장 공간의 낭비가 있다.
• 알고리즘이 복잡하다.
• 특정 자료의 탐색 시간이 많이 소요된다.

---

벡터(vector)의 장점

• 마지막 위치에 추가나 삭제가 쉽다.
• 구현이 용이하다.
• 랜덤적으로 직접접근이 가능하다.

---

벡터(vector)의 단점

• 다량의 데이터에서 검색이 느리다.
• 중간 삽입 삭제가 많은 상황에서는 비효율적이다