의견.png

"시간복잡도"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
2번째 줄: 2번째 줄:
  
 
== 개요 ==
 
== 개요 ==
알고리즘의 성능분석의 주된 요소에는 시간 복잡도와 공간 복잡도가 있다. 시간복잡도는 속도에 대한 분석결과로 알고리즘에 사용되는 연산횟수의 총량을 의미하며, 공간 복잡도는 메모리 사용량에 대한 분석결과로 알고리즘에 사용되는 메모리 공간의 총량을 의미한다. 시간복잡도는 알고리즘을 구성하는 명령어들이 몇 번 실행되는지 실행횟수를 센 결과에 각 명령어의 실행시간을 곱한 합계이다. 수행시간을 구해 시간복잡도를 구하고 해당 알고리즘이 효율적인 알고리즘인지를 판단하는데 사용한다. 다만, 각 명령어의 실행시간은 하드웨어나 프로그래밍 언어에 따라 값의 변동이 있을 수 있기때문에, 일반적으로는 실행시간을 제외하고 명령어의 실행 횟수만을 고려한다. 시간복잡도의 간단한 예를 들자면, 1을 1000000번 더하는 for 반복문이 있다고 할 때, 여기서 시간 복잡도는 10의 6승이라고 할 수 있다.  
+
알고리즘의 성능분석의 주된 요소로는 공간복잡도와 시간복잡도가 있다. 공간 복잡도는 메모리 사용량에 대한 분석결과로 알고리즘에 사용되는 메모리 공간의 총량을 의미하며, 시간복잡도는 알고리즘에 사용되는 연산횟수의 총량을 의미한다. 더 정확히는, 알고리즘을 구성하는 명령어들이 몇 번 실행되는지 실행횟수를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미한다. 주로 수행시간을 구해 시간복잡도를 구하고 해당 알고리즘이 효율적인 알고리즘인지를 판단하는 데 사용된다. 다만, 각 명령어의 실행시간은 하드웨어나 프로그래밍 언어에 따라 값의 변동이 있을 수 있기때문에, 일반적으로는 실행시간을 제외하고 명령어의 실행 횟수만을 고려한다. 시간복잡도의 간단한 예를 들자면, 1을 1000000번 더하는 for 반복문이 있다고 할 때, 여기서 시간 복잡도는 10의 6승이라고 할 수 있다. 시간복잡도를 표기하는 방법으로는 대표적으로 빅오표기법이 있다. 실행시간을 n이라고 할때 시간복잡도는 O(n)으로 표기된다. 빅오에서 가장 차수가 높은 최고차항만 두고 나머지는 버린다.  
시간복잡도를 표기하는 방법으로는 대표적으로 빅오표기법이 있다. 실행시간을 n이라고 할때 시간복잡도는 O(n)으로 표기된다. 빅오에서 가장 차수가 높은 최고차항만 두고 나머지는 버린다.  
 
  
 
* O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다. 입력데이터의 양에 상관 없이 언제나 실행시간이 일정하다. 알고리즘이 문제를 해결하는 과정에 한단계이다.  
 
* O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다. 입력데이터의 양에 상관 없이 언제나 실행시간이 일정하다. 알고리즘이 문제를 해결하는 과정에 한단계이다.  
 
* O(n): 입력 데이터의 크기에 비례하여 처리시간에 걸리는 알고리즘을 표현할 때 사용한다. 데이터의 양에 따라 시간이 정비례한다. Lenear Search, for문을 통한 탐색을 예로 들수 있다.  
 
* O(n): 입력 데이터의 크기에 비례하여 처리시간에 걸리는 알고리즘을 표현할 때 사용한다. 데이터의 양에 따라 시간이 정비례한다. Lenear Search, for문을 통한 탐색을 예로 들수 있다.  
 
* O(n^2):데이터의 양에 따라 걸리는시간은 제곱에 비례한다. 이중루프내에서 입력자료를 처리하는 경우에 발생하며, N값이 커지면 실행시간도 매우 길어져 효율성이 떨어진다.  
 
* O(n^2):데이터의 양에 따라 걸리는시간은 제곱에 비례한다. 이중루프내에서 입력자료를 처리하는 경우에 발생하며, N값이 커지면 실행시간도 매우 길어져 효율성이 떨어진다.  
* O(log n): 데이터의 양이 증가해도 시간이 조금씩 증가한다. 시간에 비례하여 탐색 가능한 데이터의 양이 2^n이 된다. 문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 사용된다. 이진 검색을 예로 들 수 있다.  
+
* O(log n): 데이터의 양이 증가해도 시간이 조금씩 증가한다. 시간에 비례하여 탐색 가능한 데이터의 양이 2^n이 된다. 문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 사용된다. 이진 검색을 예로 들 수 있다.<ref>박동건, 〈[https://velog.io/@bathingape/Time-Complexity%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84 Time Complexity(시간복잡도)]〉, 《벨로그》, 2020-01-02</ref>
  
 
시간 복잡도는 어떤 함수를 돌렸을 때 결과를 반환할 때까지 걸리는 실행시간을 의미하는 것이 아니다. 시간복잡도는 연산의 횟수를 의미하는 것이므로, 시간단위가 아니라 시행횟수 단위이다. 따라서 다음과 같은 장점을 얻는다.
 
시간 복잡도는 어떤 함수를 돌렸을 때 결과를 반환할 때까지 걸리는 실행시간을 의미하는 것이 아니다. 시간복잡도는 연산의 횟수를 의미하는 것이므로, 시간단위가 아니라 시행횟수 단위이다. 따라서 다음과 같은 장점을 얻는다.
 
* 실행이 따로 필요하지 않다.  
 
* 실행이 따로 필요하지 않다.  
 
* 소프트웨어나 하드웨어가 필요없다.  
 
* 소프트웨어나 하드웨어가 필요없다.  
* 모든 플랫폼에서 동일한 결과를 산출한다.<ref>호로요이이, 〈[https://m.blog.naver.com/demonic3540/221229805234 시간 복잡도와 공간 복잡도]〉, 《네이버 블로그》, 2018-03-15</ref><ref>박동건, 〈[https://velog.io/@bathingape/Time-Complexity%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84 Time Complexity(시간복잡도)]〉, 《벨로그》, 2020-01-02</ref>
+
* 모든 플랫폼에서 동일한 결과를 산출한다.<ref>호로요이이, 〈[https://m.blog.naver.com/demonic3540/221229805234 시간 복잡도와 공간 복잡도]〉, 《네이버 블로그》, 2018-03-15</ref>
  
 
== 계산복잡도 ==
 
== 계산복잡도 ==

2020년 7월 27일 (월) 10:51 판

시간복잡도(Time Complexity)는 컴퓨터과학 이론으로, 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 계산 복잡도 이론의 한 종류로, 알고리즘을 분석하여 효율성을 평가하는데 사용된다. 계산 복잡도 이론에는 시간복잡도 외에 공간복잡도가 있다.

개요

알고리즘의 성능분석의 주된 요소로는 공간복잡도와 시간복잡도가 있다. 공간 복잡도는 메모리 사용량에 대한 분석결과로 알고리즘에 사용되는 메모리 공간의 총량을 의미하며, 시간복잡도는 알고리즘에 사용되는 연산횟수의 총량을 의미한다. 더 정확히는, 알고리즘을 구성하는 명령어들이 몇 번 실행되는지 실행횟수를 센 결과에 각 명령어의 실행시간을 곱한 합계를 의미한다. 주로 수행시간을 구해 시간복잡도를 구하고 해당 알고리즘이 효율적인 알고리즘인지를 판단하는 데 사용된다. 다만, 각 명령어의 실행시간은 하드웨어나 프로그래밍 언어에 따라 값의 변동이 있을 수 있기때문에, 일반적으로는 실행시간을 제외하고 명령어의 실행 횟수만을 고려한다. 시간복잡도의 간단한 예를 들자면, 1을 1000000번 더하는 for 반복문이 있다고 할 때, 여기서 시간 복잡도는 10의 6승이라고 할 수 있다. 시간복잡도를 표기하는 방법으로는 대표적으로 빅오표기법이 있다. 실행시간을 n이라고 할때 시간복잡도는 O(n)으로 표기된다. 빅오에서 가장 차수가 높은 최고차항만 두고 나머지는 버린다.

  • O(1) : 입력 데이터의 크기와 상관없이 언제나 일정한 시간이 걸리는 알고리즘이다. 입력데이터의 양에 상관 없이 언제나 실행시간이 일정하다. 알고리즘이 문제를 해결하는 과정에 한단계이다.
  • O(n): 입력 데이터의 크기에 비례하여 처리시간에 걸리는 알고리즘을 표현할 때 사용한다. 데이터의 양에 따라 시간이 정비례한다. Lenear Search, for문을 통한 탐색을 예로 들수 있다.
  • O(n^2):데이터의 양에 따라 걸리는시간은 제곱에 비례한다. 이중루프내에서 입력자료를 처리하는 경우에 발생하며, N값이 커지면 실행시간도 매우 길어져 효율성이 떨어진다.
  • O(log n): 데이터의 양이 증가해도 시간이 조금씩 증가한다. 시간에 비례하여 탐색 가능한 데이터의 양이 2^n이 된다. 문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 사용된다. 이진 검색을 예로 들 수 있다.[1]

시간 복잡도는 어떤 함수를 돌렸을 때 결과를 반환할 때까지 걸리는 실행시간을 의미하는 것이 아니다. 시간복잡도는 연산의 횟수를 의미하는 것이므로, 시간단위가 아니라 시행횟수 단위이다. 따라서 다음과 같은 장점을 얻는다.

  • 실행이 따로 필요하지 않다.
  • 소프트웨어나 하드웨어가 필요없다.
  • 모든 플랫폼에서 동일한 결과를 산출한다.[2]

계산복잡도

알고리즘을 분석하는 데는 공간복잡도보단 시간복잡도가 더 많이 사용된다.

빅오표기법

각주

  1. 박동건, 〈Time Complexity(시간복잡도)〉, 《벨로그》, 2020-01-02
  2. 호로요이이, 〈시간 복잡도와 공간 복잡도〉, 《네이버 블로그》, 2018-03-15

참고 자료

같이 보기


  의견.png 이 시간복잡도 문서는 인공지능 기술에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.