时间复杂度特集

定义法计算时间复杂度

单层循环

O(n)

• 求和符号下面的是i能够取到的值域的集合，前面的1指的是每一次循环进来以后每个基本语句都会执行一次

O(logn)

线性变化嵌套循环

• 从左到右，从外层循环到内层循环写求和公式
• 解的时候从里向外解

内外变量互不干扰

内层循环取决于外层变量

指数变化嵌套循环

• 从外层循环向内层循环去写，最里面是核心语句
• 解的时候从内向外解

外层线性变化，内层指数变化，外层限制内层

• 对内层循环变量j来讲，它是每执行一次，然后进行判断，当它自增一次的时候，count++已经执行了两次

外层指数变化，内层线性变化，外层限制内层

三重循环

线性变化，外层限制内层