[Python] 복잡도 분석, 표준 입출력 방법

• 알고리즘의 효율
  
  • 공간적 효율성(연산량 대비 작은 메모리 공간)과 시간적 효율성(연산량 대비 적은 시간)
  • 효율성을 뒤집어 표현하면 복잡도(Complexity), 복잡도가 높을수록 효율성 저하
• 시간적 복잡도 분석
  • 하드웨어 환경, 소프트웨어 환경에 따라 달라짐
  • 환경적 차이로 인해 분석이 어려움
• 복잡도의 점근적 표기
  • 복잡도는 입력 크기에 대한 함수로 표기, 이 함수는 다항식
  • 이를 단순한 함수로 표현하기 위해 점근적 표기(Asymptotic Notation) 사용
  • 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법
  • ex)
    • O(Big-Oh)-표기
    • Ω(Big-Omega)-표기
    • θ(Big-Theta)-표기
• O(Big-Oh)-표기
  • 복잡도의 점근적 상한을 표시
  • ex)
    • f(n) = 2n^2-7n+4 -> O(n^2)
    • 단순히 "실행시간이 n^2에 비례"하는 알고리즘이라고 말함
  • 자주 사용하는 O-표기
    • O(1) : 상수 시간 (Constant time)
    • O(logn) : 로그(대수) 시간 (Logarithmic time)
    • O(n) : 선형 시간 (Linear time)
    • O(nlogn) : 로그 선형 시간 (Log-linear time)
    • O(n^2) : 제곱 시간 (Quadratic time)
    • O(n^3) : 세제곱 시간 (Cubic time)
    • O(2^n) : 지수 시간 (Exponential time)
• Ω(Big-Omega)-표기
  • 복잡도의 점근적 하한을 표시
  • ex)
    • f(n) = 2n^2-7n+4 -> Ω(n^2)
    • "n이 증가함에 따라 2n^2-7n+4이 cn^2보다 작을 수 없다"라는 의미, 이때 상수 c=1
    • "최소한 이만한 시간이 걸린다"
• θ(Big-Theta)-표기
  • O-표기와 Ω-표기가 같은 경우에 사용
  • "f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다"라는 의미
• 효율적인 알고리즘은 슈퍼컴퓨터보다 더 가치 O
• 값 비싼 H/W의 기술 개발보다 효율적인 알고리즘 개발이 훨씬 더 경제적

---

• 파일의 내용을 표준 입렵으로 읽어오는 방법

import sys
sys.stdin = open('input.txt','r')
sys.stdout = open('output.txt','w')

text = input()
print(text)