qqq 시간과 공간을 포괄하는 단어는 자원resource인가? computational_resource? (chkout: WpEn:Computational_resource)
qqq 현재 여기서 말하는 것은 모두 [[계산복잡도,computational_complexity]] - 계산 복잡도 이론(computational complexity theory)? 그렇다면 여기 속하지 않는 다른 '''복잡도'''가 있으면, 무엇이? 그리고 그게 서술되면 fork.. 
 저 둘이 가장 많이 언급되고 중요한 것은 확실, 그리고 둘은 trade-off 관계. AST의 [[자료구조,data_structure]] [[구현,implementation]]에서도 그렇고 [[알고리듬,algorithm]]에서도 그렇고 ....

computational과 [[algorithmic_complexity]] 관계는? ... Google:computational+complexity+vs+algorithmic+complexity 보면 별 차이 없는 듯.

[[계산,computation]], [[계산가능성,computability]], [[알고리듬,algorithm]] [[복잡도_분석,complexity_analysis]] (= algorithmic complexity?) 에서
[[시간복잡도,time_complexity]] - 알고리즘 수행 시간 분석
{

||최악의 경우 ||worst case ||수행시간이 가장 오래 걸리는 경우 ||
||최선의 경우 ||best case ||수행시간이 가장 적게 걸리는 경우 ||
||평균적인 경우 ||average case || ||

가장 좋은 경우는 constant time
보통 polynomial time이 걸리면 reasonable

까다로움? 다루기어려움? intractability .... [[intractability]] WtEn:intractability
~~intractable한 문제: polynomial time에 풀 수 있는 문제~~
tractable한 문제: polynomial time에 풀 수 있는 문제
intractable한 문제: polynomial time에 풀 수 없는 문제
intractability는 [[알고리듬,algorithm]]의 성질이 아니라 [[문제,problem]]의 성질임.[* https://www.youtube.com/watch?v=oofvmRAOyiM 4m]
 ''think: 한 문제를 해결하는 algorithm은 한 가지가 아니라 여러가지임을 상기...''

관련된 표현(misc, del ok):
 ([[program]] or [[application]]의) speed, running time, performance, 
 더 작은 시간복잡도의 algorithm으로 바꾸는 것은 program [[최적화,optimization]]의 일종

상수시간 constant time
선형시간 linear time - ex. 선형검색 linear_search
로그시간 logarithmic time - ex. 이진검색 binary_search
지수시간 exponential time

Twins:
[[WpKo:시간_복잡도]]
[[WpEn:Time_complexity]]
https://everything2.com/title/Time+complexity
[[Namu:시간%20복잡도]]

Up: [[시간,time]] [[복잡도,complexity]]
}
[[공간복잡도,space_complexity]] - [[알고리즘,algorithm]]이 쓰는 기억 공간,,[[메모리,memory]]. +storage?,, 분석
보통 문제(입력?) 크기 $n$ 에 대한 [[함수,function]]으로 나타냄

algorithmic complexity
computational complexity (=time complexity?)

Sub:
game_complexity - writing; [[게임이론,game_theory]]의 복잡도.

<<tableofcontents>>

= Big O notation =
chk 1:

이건 관용적으로 ∈ 자리에 =를 허용해주는 것 같다...?
i.e. 사실은 [[집합,set]] 포함 관계로 하면 더 정확한 f(n)∈O(g(n)) 이것을 f(n)=O(g(n))으로 (다들 표기해도 아무 문제없다고 보는 듯) or (그냥 간단히 표기하는 게 대세인듯)

chk 2:
O(1) ⊂ O(n)  ⊂ ...  ⊂ O(n^^2^^) ⊂ ...  ⊂ O(2^^n^^) ...?

----
[[점근표기법,asymptotic_notation]](writing)
{
[[부등식,inequality]]을 사용하여 정의한다.

두 함수 $f(n)$ 과 $g(n)$ 이 주어졌을 때,
모든 $n>n_0$ 에 대하여,
$|f(n)|\le c|g(n)|$ 을 만족하는 두 상수 $c,\,n_0$ 가 존재하면
$f(n)=O(g(n))$ 이다.

이것은 $g$ 가 $f$ 의 상한값이라는 것이다.
||빅오      ||상한 ||
||빅오메가  ||하한 ||
||빅세타    ||? ||

자주 나오는 빅오 표기
||$O(1)$       ||상수형 ||
||$O(\log n)$  ||로그형 ||
||$O(n)$       ||선형 ||
||$O(n\log n)$ ||선형로그형 ||
||$O(n^2)$     ||2차형 ||
||$O(n^3)$     ||3차형 ||
||$O(2^n)$     ||지수형 ||
||$O(n!)$      ||팩토리얼형 ||

----
// SNU이광근 컴여세 p100

전제: 입력의 크기 $n$

계산 비용이 입력이 커지면서 결국 어떤 함수 $f(n)$ 의 상수곱(상수배?)를 넘지 않으면 $O(f(n))$ 이라고 쓴다.
함수의 가장 차수가 높은 [[항,term]]만 남기고 [[계수,coefficient]]는 무시.

(현재까지) n×n 행렬을 곱하는 가장 빠른 algorithm은 // [[,matrix_multiplication]]
 O(n^^2.3728639^^) Google:Coppersmith-Winograd
 [[Date(2021-11-13T23:31:41)]] : see [[WpEn:Computational_complexity_of_matrix_multiplication]]
n자리 정수 두 개를 빠르게 곱하는 algorithm은 // [[곱셈,multiplication]]
 O(n^^1.585^^) Srch:Karatsuba 곱
 {
  [[WpKo:카라추바_알고리즘]]
  [[WpEn:Karatsuba_algorithm]]
  [[https://brilliant.org/wiki/karatsuba-algorithm/]]
 }

----
Links (한국어)
https://johngrib.github.io/wiki/big-O-notation/
}


∀c, ∃n,,0,,
such that
f(n) ≤ cg(n) for all n ≥ n,,0,,
https://xlinux.nist.gov/dads/HTML/bigOnotation.html

= Big Ω notation =
빅오메가 표기법
{
두 함수 $f(n)$ 과 $g(n)$ 이 주어졌을 때,
모든 $n>n_0$ 에 대하여,
$|f(n)|\ge c|g(n)|$ 을 만족하는 두 상수 $c,\,n_0$ 가 존재하면
$f(n)=\Omega(g(n))$ 이다.
}

https://mathworld.wolfram.com/Big-OmegaNotation.html
https://xlinux.nist.gov/dads/HTML/omegaCapital.html

= Big Θ notation =
빅세타 표기법
{
두 함수 $f(n)$ 과 $g(n)$ 이 주어졌을 때,
모든 $n>n_0$ 에 대하여,
$c_1|g(n)| \le |f(n)| \le c_2|g(n)|$ 을 만족하는 세 상수 $c_1,\,c_2,\,n_0$ 가 존재하면
$f(n)=\Theta(g(n))$ 이다.
}

https://mathworld.wolfram.com/Big-ThetaNotation.html
https://xlinux.nist.gov/dads/HTML/theta.html

= Little o Notation =
∀c, ∃n,,0,,
such that
f(n) < c g(n) for all n ≥ n,,0,,

'subquadratic or o(N^^2^^) time' (Weiss Java p357)

https://xlinux.nist.gov/dads/HTML/littleOnotation.html
https://mathworld.wolfram.com/Little-ONotation.html

WpEn:Little-o_notation redir. to: [[WpEn:Big_O_notation#Little-o_notation]]

----
[[Date(2022-12-24T08:37:25)]]
o(x)에 대해 일단 여기에 임시로 적어놓음 ...

later fork to [[Little_o_notation]]
rel. [[Landau_symbol]] ( https://mathworld.wolfram.com/LandauSymbols.html )
... Google:little+o+function 

//// 이하 김홍종 ////
$o(x^n)$
실수체의 원점 근방에서 정의된 함수 $f(x)$ 가 $f(0)=0$ 이고, 어떤 자연수 $n$ 에 대해
 $\lim_{x\to 0}\frac{f(x)}{x^n}=0$
이면, 함수 $f(x)$ 가 원점 근방에서 0으로 수렴하는 정도는 $x^n$ 이 0으로 수렴하는 정도보다 훨씬 빠르다. 이와 같은 함수 $f$ 를
 $|f(x)| \ll |x^n|$ 또는
 $f(x)=o(x^n)$ 또는
 $f(x)\in o(x^n)$
등으로 표시하고, "f 는 (원점 근방에서) o(x^^n^^)이다" 또는 "f(x)는 x^^n^^보다 절대적으로 아주 작다"고 말한다.
보기를 들면, 어떤 거듭제곱급수(=[[멱급수,power_series]]) 함수 $u(x)$ 에 대하여
 $\cos x = 1-\frac12 x^2 + x^4 u(x)$
로 표현되므로
 $\cos x - 1 + \frac12 x^2 = o(x^3)$
이다.

(정리 3.2.2) 다음은 원점 근방에서 정의된 $n$ 번 미분가능한 함수 $f(x)$ 가 $o(x^n)$ 일 필요충분조건이다:
 $f(0)=0,\; f'(0)=0,\; \cdots,\; f^{(n)}(0)=0.$
(증명) 만약 $f(0)=f'(0)=\cdots=f^{(n-1)}(0)=0$ 이면 [[로피탈_정리,L_Hopital_s_rule]]에서
 $\lim_{x\to 0} \frac{f(x)}{x^n} = \lim_{x\to 0} \frac{f'(x)}{nx^{n-1}} = \cdots = \lim_{x\to 0}\frac{f^{(n-1)}(x)}{n!x} = \frac{f^{(n)}(0)}{n!}$ ..... (1)
을 얻는다.
따라서 $f(0)=f'(0)=\cdots=f^{(n-1)}(0)=f^{(n)}(0)=0$ 이면
 $\lim_{x\to 0} \frac{f(x)}{x^n} = \frac{f^{(n)}(0)}{n!} = 0,$
즉
 $f(x)=o(x^n)$
이다. 역으로
 $f(x)=o(x^n) \;\Rightarrow\; f(0)=f'(0)=\cdots=f^{(n)}(0)=0$ ..... (2)
임을 자연수 $n$ 에 대한 [[수학적귀납법,mathematical_induction]]을 써서 밝힌다.
$n=1$ 일 때에는 이미 앞에서 살펴본 명제이다.
이제 $n>1$ 이라고 가정하자. $f(x)=o(x^n)$ 이면 $f(x)=o(x^{n-1})$ 이고, 따라서 귀납법의 가정( $n-1$ 번째 명제가 참이라는 가정 )에 의하여
 $f(x)=o(x^{n-1}) \;\Rightarrow\; f(0)=f'(0)=\cdots=f^{(n-1)}(0)=0$
임을 안다. 그러므로 (1)에서
 $0=\lim_{x\to 0}\frac{f(x)}{x^n} = \frac{f^{(n)}(0)}{n!}$
을 얻는다. 따라서 (2)가 참이다.

(김홍종 미적1+ p120-122, [[선형근사,linear_approximation]] 설명 중 언급)
(저기선 원점에서의 일차근사다항식을 $f(x)=f(0)+f'(0)x+o(x)$ 로 설명)

= Little ω Notation =
https://xlinux.nist.gov/dads/HTML/omega.html

= 이상 =
rel.
Landau_symbol https://mathworld.wolfram.com/LandauSymbols.html
https://mathworld.wolfram.com/AsymptoticNotation.html


= P, NP 대략적 설명 =
Roughly,

P = the set of all decision problems that are "efficiently solvable"
NP = the set of all decision problems that are "efficiently verifiable"
NPC = { x | x is a decision problem that has the following 2 properties at the same time:
             (1) x is a member of NP
             (2) "all" problems in NP are "efficiently reducible to x }

in Korean

P 는 해결이 효율적으로 되는 모든 결정문제들의 집합
NP 는 검증이 효율적으로 되는 모든 결정문제들의 집합
NPC = { x | x 는 다음 두가지 특성을 동시에 만족하는 [[결정문제,decision_problem]]:
            (1) x 는 NP 의 원소
            (2) NP 안의 "모든" 문제들은 x 로 효율적으로 reduce 됨 }

(박성빈)
----
https://i.imgur.com/lbJTJ52.gif
See http://www.aistudy.com/pioneer/Cook_Levin.htm
----
계산 복잡도 입문 (Linz의 저서 '형식 언어와 오토마타', page 361-374)
http://www.aistudy.com/linguistics/complexity_linz.htm

= P =

= NP =
NP 는 nondeterministic polynomial (비결정성 다항식) 의 머리 글자

[[WpKo:NP_(복잡도)]]
{
NP의 뜻: __n__ondeterministic __p__olynomial time.
어떤 [[문제,problem]]의 [[집합,set]].
NP에 속하는 문제는 [[비결정론적_튜링_기계]] nondeterministic_Turing_machine (NTM) 로 다항 시간 안에 풀 수 있는 판정문제([[결정문제,decision_problem]])의 집합.

NP에 속하는 문제는 [[결정론적_튜링_기계]] deterministic_Turing_machine (DTM) 로 다항시간에 검증''(무엇을 검증?)''이 가능하고, 그 역도 성립.

DTM으로 다항시간안에 풀 수 있는 문제는 NTM으로도 다항시간 안에 풀 수 있으므로, P는 NP의 부분집합. 하지만 P가 NP의 진부분집합인지 여부는 밝혀지지 않음 - [[P-NP문제,P-NP_problem]]
}

= NP-hard,NP-난해 =

= NP-complete,NP-완전 =
NP-hard이면서 NP class안에 있는 문제는 NP-complete? chk

https://complexityzoo.net/Complexity_Zoo:N#npc

= P-NP 문제 =


[[WpKo:P-NP_문제]]
[[문제,problem]]

= Kolmogorov complexity =
// Kolmogorov_complexity
만족스럽게도, Kolmogorov complexity $K$ 는 근사적으로 [[엔트로피,entropy|Shannon entropy]] $H$ 와 같다 if the sequence is drawn at random from a distribution that has entropy $H.$ 그래서 [[정보,information]] 이론과 매우 밀접하다.
(p3)
The Kolmogorov complexity of a binary string is defined as the length of the shortest computer program that prints out the string.
(Cover Thomas p6)
Occam's Razor (The simplest explanation is best.)와 관련.

= tmp; cleanup; to mv =
https://mathworld.wolfram.com/AsymptoticNotation.html
https://everything2.com/title/Little+o+notation
https://everything2.com/title/Landau+equivalent

----
complexity는 [[입력,input]] 크기 $n$ 에 대한 [[함수,function]]로 나타난다.

● 현실적인 [[알고리듬,algorithm]]:
복잡도가 입력 크기 $n$ 의 상수제곱이면 현실적인 algorithm이라고 본다. (polynomial_complexity) - [[다항식,polynomial]] [[다항함수,polynomial_function]]
 $n^k$

다항 알고리듬이 있는 [[문제,problem]]
 ≅ 현실적인 비용으로 풀 수 있는 문제
 ≅ P 클래스 문제

● 비현실적인 algorithm:
상수(>1)의 지수배 제곱. (exponential_complexity) - [[지수,exponentiation]] [[지수함수,exponential_function]]
 $k^n$

(이광근 컴여세)

= 복잡도 관련 정리들 ''theorems on/about complexity?'' =
[[정리,theorem]]

See https://complexityzoo.net/Complexity_Dojo
 mentions:
 Cook-Levin_theorem
 Savitch_theorem
 Ladner_theorem

= Links ko =
복잡성 이론 complexity theory (2003, essay, 임백준, 행복한 프로그래밍)
http://www.aistudy.com/computer/complexity_lim.htm
mentioned: Hamiltonian_path TSP traveling_salesman_problem 

= Links en =
복잡도의 종류는 매우 매우 다양함.
https://complexityzoo.net/

http://foldoc.org/contents/complexity.html

= Misc. / Rel. =
이름은 비슷. 관계? 차이? [[복잡계,complex_system]]

단어 complex와 complicated 의 의미차? Google:complex+complicated+difference Google:complex+complicated+차이 Naver:complex+complicated+차이

http://www.scholarpedia.org/article/Complexity
이건 복잡도보다는 복잡성? Rel. [[복잡계,complex_system]]

----

WpEn:Computational_complexity

WpKo:계산_복잡도_이론
WpEn:Computational_complexity_theory
https://mathworld.wolfram.com/ComplexityTheory.html

WpKo:복잡도_종류
WpEn:Complexity_class

Wiki:CategoryComplexity

Up: [[전산학,compsci]]