程序员科普:什么是时间复杂度?
本文由 简悦 SimpRead 转码, 原文地址 https://new.qq.com/omn/20180827/20180827A0NEVH.html
作者小灰
如需转载,请联系原作者授权。
时间复杂度的意义
究竟什么是时间复杂度呢?让我们来想象一个场景:某一天,小灰和大黄同时加入了一个公司……
一天过后,小灰和大黄各自交付了代码,两端代码实现的功能都差不多。大黄的代码运行一次要花 100 毫秒,内存占用 5MB。小灰的代码运行一次要花 100 秒,内存占用 500MB。于是……
由此可见,衡量代码的好坏,包括两个非常重要的指标:
1. 运行时间;
2. 占用空间。
基本操作执行次数
关于代码的基本操作执行次数,我们用四个生活中的场景,来做一下比喻:
场景 1:给小灰一条长 10 寸的面包,小灰每 3 天吃掉 1 寸,那么吃掉整个面包需要几天?
答案自然是 3 X 10 = 30 天。
如果面包的长度是 N 寸呢?
此时吃掉整个面包,需要 3 X n
...