bigO對應到的input大小

January 31, 2021 · 1 min · zhengcf

Table of Contents

動機
上結論
Ref

動機

一直很疑惑input與bigO之間的n大概是多少，所以把參考的表格存一份在這裡

上結論

Length of Input (N)	Worst Accepted Algorithm
$\le [10..11]$	$O(N!), O(N^6)$
$\le [15..18]$	$O(2^N * N^2)$
$\le [18..22]$	$O(2^N * N)$
$\le 100$	$O(N^4)$
$\le 400$	$O(N^3)$
$\le 2K$	$O(N^2 * logN)$
$\le 10K$	$O(N^2)$
$\le 1M$	$O(N * logN)$
$\le 100M$	$O(N), O(logN), O(1)$

Ref

Time and Space Complexity