时间复杂度

发表于 | 分类于 ， | 阅读次数
字数统计 | 阅读时长
时间复杂度（Java为例）

       看如下代码：

1
2
3
4
5
6
7
8
9
10
11
Person[] perArr = new Person[10];
perArr[0] = new Person("张三", 21);
perArr[1] = new Person("李四", 19);
perArr[2] = new Person("王五", 20);
perArr[3] = new Person("赵六", 42);
perArr[4] = new Person("孙七", 30);
perArr[5] = new Person("周八", 18);
perArr[6] = new Person("钱九", 45);
perArr[7] = new Person("吴十", 13);
perArr[8] = new Person("冯十一", 63);
perArr[9] = new Person("朱十二", 27);

       假如我们想知道小组里周八的年龄，相信大家都会写代码去找：

1
2
3
4
5
6
7
for (int i = 0; i < perArr.length; i++) {
    if ("周八".equals(perArr[i].getName())) {
        System.out.println("循环取值，周八的年龄是：" + perArr[i].getAge());
        System.out.println("循环了" + i + "次");
        break;//已经找到了周八，跳出循环
    }
}

       需要循环取6次从数组里获取Person对象。

       如果知道周八在小组的第5个位置（数组下标5），不用循环，我们直接找就是：

1
2
Person person = perArr[5];
System.out.println("取第5个位置，" + person.getName() + "的年龄是：" + person.getAge());

       无论数组中有多少个元素，每次去读取元素并比较的时间总是相同的，假设这个时间为K，在上面示例中在数组中循环搜索某个用户，我们循环了6次才搜索到该用户，时间为6*K。

       在现实中，我们用来计算时间的长短，一般单位有小时，分钟，秒等，同样我们也需要一种度量来计算本示例中的算法的效率，在计算机科学中，这种度量方法被称为“大O”表示法。

       当我们知道元素的位置，一步到位就能访问到该元素，这个时间为K，时间复杂度用大O表示法标记为O(1)，省略了K。而在数组中查找某元素，我们并不知道这个元素在数组的什么位置，假设数组的长度为n，有可能该元素刚好在数组的下标为0的位置（第一个位置）循环1次就匹配到了，时间复杂度为O(1)。也有可能在数组下标为n-1的位置（最后一个位置）我们要循环n次才能匹配到该值，时间复杂度为O(n)。假设每次匹配的元素都在数组的最后一位，这是一种运行时间保证，运行时间不会再长了，即在数组中查找某元素，时间复杂度为O(n)。

       在长度为n的数组中，直接通过下标去访问元素，时间复杂度为O(1)；需要循环查找元素的时候，时间复杂度为O(n)。

参考资料：
清浅池塘 时间复杂度

Fork me on GitHub