• 배열 vs 리스트

    - 배열 (array)
     : 연속된 주소공간, 선형 자료 구조
     : 직접 접근 O(1), 순차 접근 O(n) 가능
     : 정적메모리 할당, 지역변수로는 메모리 제한, 메모리 낭비

    - 리스트 (list)
     : 연속된 공간이 아니며, 이전 노드나 다음 노드를 가르키는 주소값 필요, 선형 자료 구조
     : 헤드포인터 필요
     : 순차 접근 O(n) 가능
     : 동적메모리 할당, 필요한 만큼 할당
      


'Major > Data structures' 카테고리의 다른 글

자료구조 - 이진트리  (0) 2015.11.12
자료구조 - 트리  (0) 2015.11.12
자료구조 - 데크  (0) 2015.11.12
자료구조 - 큐  (0) 2015.11.12
자료구조 - 스택  (0) 2015.11.12
  • 재귀 함수 구현
    1. 기저 파악 (재귀를 멈추는 부분, 끝 조건)
    2. 조건문 파악 (재귀 호출 조건)
    3. 구현

    - 거듭제곱 값, 피보나치 수열, 하노이탑

    - 반복 vs 재귀
     : 상황에 따라 속도가 더 빠른 것을 선택
     : 재귀는 스택오버플로우가 일어날 수 있다.


'Algorithm' 카테고리의 다른 글

알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12
알고리즘 - 복잡도 분석  (0) 2015.11.12
알고리즘 문제 풀이 주의사항  (0) 2015.11.05
C/C++, JAVA 데이터 형식 범위  (0) 2015.11.05
  • 빅오 표기법



    O(1)상수항상 일정한 속도를 가진다.
    O(Log(N))로그N이 증가함에 따라 조금식 시간이 늘어난다.
    O(N)선형N이 증가하면 시간도 일정하게 증가한다.
    O(NLog(N))선형로그N이 2배로 증가하면 실행 시간은 두배 보다 약간 더 많이 늘어 난다.
    O(N^2)평방형N이 증가시 2 제곱만큼 실행 시간이 늘어 난다.(이중 루프 처리시)
    O(2^N)지수형N이 증가할수록 실행 시간은 급격히 늘어 난다.
    O(N!)계승형N이 증가할수록 실행 시간은 졸라 급격히 늘어 난다.(팩토리얼)


  • 표기법

    - O(Big-O)

     : 상한, 최악의 경우(Worst Case)를 나타내는 표기법으로 알고리즘 분석에서 가장많이 사용하는 표기법이다.

    - Ω(Omega)
     : 하한, 최상의 경우(Best Case)를 나타내는 표기법이다.

    - θ(Theta)
     : 평균의 경우(Average Case)를 나타내는 표기법이다.


'Algorithm' 카테고리의 다른 글

알고리즘 - 삽입 정렬  (0) 2015.11.12
알고리즘 - 선택 정렬  (0) 2015.11.12
알고리즘 - 재귀 호출  (0) 2015.11.12
알고리즘 문제 풀이 주의사항  (0) 2015.11.05
C/C++, JAVA 데이터 형식 범위  (0) 2015.11.05

+ Recent posts

티스토리툴바