Question

（一）算法之时间复杂度理解

Answer 1

前言

相信学过C语言的都知道算法：冒泡排序、选择排序、快速排序等等。

那么，关于时间复杂度O(n)、O(logn)这个概念应该怎么理解呢？

本篇为你讲述

正文

《数据结构》（严蔚敏、吴伟民编著)中有句话：“整个算法的执行时间与基本操作重复执行的次数成正比”，基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O(f(n)) ，也就是算法之行时间,其中f(n)为T(n)的同数量级函数，即T(n)/f(n) = 常数。“语句频度”定义：该语句重复执行的次数。如果是基本操作所在语句重复执行的次数，那么就该是f(n)。

一、冒泡排序，时间复杂度为O(n^2).

为了理解，首先举个例子，for循环遍历一个长度为n的数组

for(int i = 0;i < n;i++) {

a[i] = 0;  //重复操作执行n次

}

那么次循环的时间复杂度就是O(n),若是两层for循环

for(int i = 0;i < n;i++) {

a[i] = 0;  //重复操作执行n次

        for（int j = 0;j < n;j++){

            b[i] = 1; //重复执行n^2次

        }

}

那么此时T(n) = n + n^2，令f(n) = n^2, T(n)/f(n) = 1/n + 1;当n->∞，T(n)/f(n) =1为常数，则T(n) = O(n^2);

那么对于冒泡排序，就好理解了，两层for循环，时间复杂度为O(n^2)。同理，选择排序也是O(n^2)。

二、对于二分搜索，其时间复杂度为O(logn)。

二分搜索指的是对一个已经排好序的数组、先查找中间元素，如果中间元素小于要查找的值，则继续查找大于中间元素的那一部分。反正则查找小于中间元素，这样每次都能减少1/2的查找范围。

对于n个元素的数组进行二分搜索。

第一次二分查找剩下： n/2 个元素

第二次二分剩下：n/4个元素

第三次二分剩下：n/8个元素

第m次二分剩下：n/(2^m)个元素

在最坏情况下是在排除到只剩下最后一个值之后得到结果，所以为n/(2^m)=1; 则m = log2(n);

所以其时间复杂度为O(log2(n)).那么O(logn)是什么意思？log的底数为？

计算机思想中有一种叫做分治思想，即不管是二分还是三分、其次数和复杂度上只是一个常数上的差别。

例如 log3(n) / log2(n)，根据数学换低公式， log3(n) / log2(n) = ln(n) / ln(3) * ln(2) / ln(n) = ln(2)/ln(3)为一个常数，当我们将n取一个非常大的数字，n->∞，我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。所以O（logn）已经可以表达所有底数的对数了。

总结：

计算时间复杂度，1，首先看有几重for循环，只有一重则时间复杂度为O(n),两重则为O(n^2),依次类推。2，如果有二分(或三分)则为O(logn),如果一个for循环套一个二分，那么时间复杂度为O(nlogn)。