시간복잡도

시간복잡도(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이 된다. 문제를 해결할 때 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다. 문제를 일정한 크기의 작은 문제로 분리할 때 사용된다. 이진 검색을 예로 들 수 있다.

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

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

계산복잡도

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

참고 자료

• 시간복잡도 위키백과 - https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84
• 호로요이이, 〈시간 복잡도와 공간 복잡도〉, 《네이버 블로그》, 2018-03-15
• 박동건, 〈Time Complexity(시간복잡도)〉, 《벨로그》, 2020-01-02

같이 보기

• 알고리즘
• 공간복잡도

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

인공지능 : 인공지능 서비스, 인공지능 로봇, 인공지능 기술 □■⊕, 인공지능 기업, 인공지능 인물 인공지능 기술 AI 워싱 • 랭체인 • 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지능 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 • 프롬프트 • 프롬프트 엔지니어링 문자인식과 음성인식 ICR • OCR • OMR • TTS • URL • 글자 • 단어 • 답변 • 대화 • 동영상 • 디자인 • 맥락 • 문단 • 문서 • 문자 • 문자인식 • 문자채팅 • 문장 • 발음 • 번역 • 분류 • 상담 • 소스코드 • 스토리 • 얼굴 • 얼굴인식 • 음성 • 음성채팅 • 음성인식(STT) • 이미지 • 인공어 • 인공지능 음성 • 자막 • 자연어 • 질문 • 채팅 • 코드 • 코딩 • 텍스트 • 통번역 • 통역 • 파일 • 폴더 • 화상채팅 • 화자인식 인공지능 데이터 데이터라벨러 • 데이터라벨링 • 데이터셋 • 돌마 • 벡터 • 벡터DB • 벡터공간 • 스칼라 • 임베딩 • 청크(Chunk) • 크라우드워커 • 토큰 • 토큰화 인공지능 학습 ADP • CoLLM • DALL-E • DDPG • DQN • LAM • LMM • SARSA • sLLM • SLM • 강화학습 • 거대언어모델(LLM) • 결정이론적 메타추론 • 계통적 강화학습 • 과적합 • 동적 계획법 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 메타추론 • 모델 기반 강화학습 • 모델 프리 강화학습 • 미세조정(파인튜닝) • 반영식 아키텍처 • 비지도학습 • 사전학습 • 수시 알고리즘 • 어니 • 에이전트 • 인공지능 학습 • 전이학습 • 준지도학습 • 지도학습 • 추론 • 학습 • 확률적 경사하강법 인공지능 알고리즘 AGI • ANI • ASI • RAG • XAI • 가중치 • 관계형 네트워크(RN) • 뉴런 • 다층퍼셉트론 • 단층퍼셉트론 • 데이터마이닝 • 방사신경망 • 볼츠만 머신 • 분산 샌드박스 • 생성대립신경망(GAN) • 생성형 AI • 수퍼얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그모이드 함수 • 신경망 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 은닉층 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 주의 메커니즘 • 코헨 자기조직 신경망 • 텍스트마이닝 • 트랜스포머 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 계산복잡도 NP • NP-완전 • 계산복잡도 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 프로그램 BCI • GPT • 딥블루 • 딥페이크 • 멀티모달 AI • 모달 • 모달리티 • 모달창 • 알렉스넷 • 어니 • 알파고 • 알파고제로 • 알파폴드 • 왓슨 • 카페 • 컨트롤넷 • 텐서플로 • 텔레파시 • 토치 • 파이토치 • 한돌 인공지능 특징 결정이론 • 계산상의 합리성 • 논리학 • 논리주의자 • 분산성 • 불확실성 • 삼단논법 • 선호도 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 최대기대효용 • 할루시네이션 • 효용이론 인공지능 법적 지위 권리주체성 • 소버린 AI • 전자대리인 • 전자적 인간 • 책임법 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반