演算法

1// O(1): one step, whatever n is.
2function constantSteps(n: number): number {
3  return 1;
4}
5 
6// O(log n): binary search for a value larger than everything.
7function logSteps(n: number): number {
8  let lo = 0, hi = n - 1, steps = 0;
9  while (lo <= hi) {
10    steps++;
11    const mid = (lo + hi) >> 1;
12    lo = mid + 1;
13  }
14  return steps;
15}
16 
17// O(n): look at every element once.
18function linearSteps(n: number): number {
19  let steps = 0;
20  for (let i = 0; i < n; i++) steps++;
21  return steps;
22}
23 
24// O(n log n): one binary search per element.
25function linearithmicSteps(n: number): number {
26  let steps = 0;
27  for (let i = 0; i < n; i++) steps += logSteps(n);
28  return steps;
29}
30 
31// O(n^2): every pair once.
32function quadraticSteps(n: number): number {
33  let steps = 0;
34  for (let i = 0; i < n; i++) {
35    for (let j = i + 1; j < n; j++) steps++;
36  }
37  return steps;
38}
39 
40// O(2^n): every subset of n items.
41function exponentialSteps(n: number, i = 0): number {
42  if (i === n) return 1;
43  return exponentialSteps(n, i + 1) + exponentialSteps(n, i + 1);
44}