时间复杂度和空间复杂度分析
时间复杂度和空间复杂度分析
为什么要追求时间复杂度
对数
理解复杂度先来理解一个高中数学概念对数。
16世纪到17世纪是天文、航海、工程、贸易、军事等方面的发展的重要时期，数据不能满足自然科学等方面的发展，约翰·纳皮尔（J.Napier，1550-1617）在研究天文学的过程中为了简化计算发明了对数。对数的发明是数学历史上的重大发明，对当时的自然科学等学科的发展起到了重要作用，恩格斯曾经把对数、解析几何、微积分并称为17世界数学的三大成就。伽利略也说过：给我空间、时间、和对数，我们就可以创造一个宇宙，是不是跟阿基米德说过的：给我一个支点，我就能撬动整个地球。虽然很玄幻，继续看下去就会发现真的是很有道理的。 一个些简单的对数：
lg10000 = log1010000 表示10的y次方等于 10000
lg1000 = log101000 表示10的y次方等于1000
lg100 = log10100 表示10的y次方等于100
lg10 = log1010 表示10的y次方等于10
lg1 = log101 表示10的多少次方等于0
用公式来表示 log10 N = y，把数字代入N就可以求出y，同理把数字代入y，也能求出N。
log2 2 表示2的y次方等于 2
log2 4 表示2的y次方等于4
log2 8 表示2的y方等于8
log2 16 表示2的y次方等于16
用公式来表示log2 N = y，同理把数字代入N，就可以求出y的值
对数的问题讲完了。
下面我们看一个棋盘麦粒问题，然后用对数来表示。
棋盘麦粒问题
在印度有一个古老的传说：舍罕王打算奖赏国际象棋的发明人——宰相：西萨·班·达依尔。国王问他想要什么，他对国王说：“陛下，请您在这张棋盘的第1个小格里，赏给我1粒麦子，在第2个小格里给2粒，第3小格给4粒，以后每一小格都比前一小格加一倍。请您把这样摆满棋盘上所有的64格的麦粒，都赏给您的仆人吧！”国王觉得这要求太容易满足了，就命令给他这些麦粒。当人们把一袋一袋的麦子搬来开始计数时，国王才发现：就是把全印度甚至全世界的麦粒全拿来，也满足不了那位宰相的要求。
假如不考虑空间问题，要多少粒麦子才可以放满棋盘呢，国王的仆人能得到多少麦粒呢？
从上文得到放麦粒的规则是第一个棋盘1粒、第二个棋盘2粒、第三个棋盘4粒，每一个格子都是前一个格子的2倍，象棋一共有8*8=64格子，直接是没法写出来的
1
1 + 2 + 4 + 8 + ……
先把格子列出来
1
1 2 3 4 …… 60 61 62 63 64
改写成平方的写法
20 + 21 + 22 + 23 + 24 + 25 + 26 + 27 + 28 + …… + 260 + 261 + 262 + 263
我们知道5个格子可以计算 20 + 21 + 22 + 23 + 24 = 1 + 2 + 4 + 8 + 16 = 1 + 30 = 31
可以得出 20 + 21 + 22 + 23 + 24 = 25 - 1
那么64个格子可以写成264 -1 = 18446744073709551615
设棋盘格子数量是y，麦粒的数量是x, N - 1 = x，N的对数表示为log2 N = y，
那么先求出N，然后N - 1就等于麦粒的个数了，第一个棋盘的麦粒略去，
那么代入对数表示法中：log2 N = 64，这里只有一个未知数N，即可以求出N的值。
1
2
3
4
5
6
7
8
// javascript丢失了4位精度，实际的值应该是18446744073709551616
let sum = Math.pow(2, 64)
console.log(`填满国际象棋需要麦粒 ${sum} 颗`)
// 输出 填满国际象棋需要麦粒 18446744073709552000 颗
// 验算
let N = 18446744073709551616
let y = Math.log2(N)
console.log(`一共有 {y} 格棋盘`)
1
2
3
4
5
6
7
8
# -*- coding: UTF-8 -*-
# 填充国际象棋棋盘
from math import *
print("填满国际象棋需要麦粒 %d" %(pow(2, 64)))
# 输出 填满国际象棋需要麦粒 18446744073709551616
// 验算
print("一共有 %d 格棋盘" % log2(18446744073709551616))
```java import java.math.BigInteger;
class Demo { public static void main(String[] args) throws java.lang.Exception { BigInteger sum = BigInteger.ONE; BigInteger b = new BigInteger(“2”); for (int i = 1; i 2，还可以是其他的任何一个可以代入n并得到执行次数的函数的计算和表示方法。