时间复杂度和空间复杂度分析
时间复杂度和空间复杂度分析
为什么要追求时间复杂度
对数
理解复杂度先来理解一个高中数学概念对数。
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 + 2 + 4 + 8 + ……
先把格子列出来
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的值。
// javascript丢失了4位精度，实际的值应该是18446744073709551616
let sum = Math.pow(2, 64)
console.log(`填满国际象棋需要麦粒 ${sum} 颗`)
// 输出 填满国际象棋需要麦粒 18446744073709552000 颗
// 验算
let N = 18446744073709551616
let y = Math.log2(N)
console.log(`一共有 {y} 格棋盘`)
# -*- coding: UTF-8 -*-
# 填充国际象棋棋盘
from math import *
print("填满国际象棋需要麦粒 %d" %(pow(2, 64)))
# 输出 填满国际象棋需要麦粒 18446744073709551616
// 验算
print("一共有 %d 格棋盘" % log2(18446744073709551616))
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 <= 64; i++) {
sum = sum.multiply(b);
}
// sum = sum.subtract(BigInteger.ONE);
System.out.println("填满国际象棋需要麦粒 " + sum);
// 验算
double girdNum = Math.log(sum.doubleValue()) / Math.log(2);
System.out.println("一共有 " + String.valueOf(girdNum) + " 格棋盘");
}
}
时间复杂度的差别
对数表示是log2 N = y、log10 N = y、loge N = y，这里的e是常数e,约等于2.718281828459045
先来比较两个对数，分别求y的值
log1018446744073709551616 = y = 19.265919722494793
log218446744073709551616 = y = 64
可以看相同的N的值使用log以10为底数和log以2为底数，计算的y的值变化不大。
再来比较两个对数，求N的值
log10N = 64，N = 18446744073709551616
log2N = 63， N = 9223372036854775808
二者的y值只差了1，N却相差9223372036854775808，失之毫厘谬以千里都没法诠释，这就是指数的威力，也就是算法为什么要追求时间复杂度的原因。
所以在算法中讨论时间复杂度时，不会去纠结底数是2和10，就像O(1)和,O(2),O(3),O(4)
都算作O(1)，而O(N)和O(N2)差别是巨大的。
如何计算和时间复杂度
时间复杂度并不只是用对数来表示的，还有其他的方式来表达，用对数来举例只是为了明白为什么时间复杂度这么重要，也方便理解怎么计算时间复杂度，
时间复杂度的表示方法是使用大写字母O()表示，括号内是算法执行的次数。
回过头去看棋盘放麦粒的时间复杂度，棋盘有64格子，所以就是O(64)，那如果算一个9乘9的棋盘时间复杂度就是O(81)，用n来表示棋盘的格子数，O(n)就是这个算法的时间复杂度，不管你的棋盘格子数是多少。
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 <= 64; i++) {
sum = sum.multiply(b);
}
System.out.println("填满国际象棋需要麦粒 " + sum);
}
}
下面是O(log n)的时间复杂度，n的值是64，执行了6次，时间复杂度就是log264 = 6，我们把n换成4，执行了2次，也符合log2 4 = 2，所以这个算法的时间复杂度就是O(log n)。
public class OLogn {
public static void main(String[] args) {
int n = 64;
int count = 0;
for (int i = 1; i < n; i = i * 2) {
count++;
}
System.out.println("时间复杂度" + count);
}
}
当然时间复杂度O里的表达式不一定是n、log n、n2，还可以是其他的任何一个可以代入n并得到执行次数的函数的计算和表示方法。