描述算法复杂度
<ul>
<li><a href="https://blog.csdn.net/ted_cs/article/details/82881831">https://blog.csdn.net/ted_cs/article/details/82881831</a></li>
</ul>
<h2>O(n)说明</h2>
<p>大O加上()的形式，()里面包裹的是一个函数f(),</p>
<p>O()指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。</p>
<h2>对数(log)</h2>
<p>一般地说，如果a是一个不等于1的正数，an=b时，n叫做以a为底b的<em>对数</em>，记作logab=n。</p>
<p>如5２=25中，2就叫做以5为底25的<em>对数</em>，记作log５25=2。</p>
<p>以10和e为底的对数分别叫做常用对数和自然对数，符号 分别为“lg”和“ln”。</p>
<p>利用对数可以把乘方、开方转化为乘除；乘除转化为加减，从而简化运算。</p>
<h2>O(n)类型</h2>
<table>
<thead>
<tr>
<th>类型</th>
<th>说明</th>
<th>例子</th>
</tr>
</thead>
<tbody>
<tr>
<td>O(1)</td>
<td>最低复杂度，常量值<br />耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都 不变</td>
<td>哈希算法<br /> (不考虑哈希冲突)</td>
</tr>
<tr>
<td>O(n)</td>
<td>数据量增大几倍，耗时也增大几倍</td>
<td>遍历算法</td>
</tr>
<tr>
<td>O(n^2)</td>
<td>对n个数据排序，需要扫描n*n次</td>
<td>冒泡算法</td>
</tr>
<tr>
<td>O(logn)</td>
<td>当数据增大n倍时，耗时增大logn倍<br />log以2为底，如当数据增大256倍时，耗时只增大8倍</td>
<td>二分查找<br />每找一次排一半的可能<br />256个数据中查找只要8次就可以找到目标</td>
</tr>
<tr>
<td>O(nlogn)</td>
<td>n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍<br />这个复杂度高于线性低于平方</td>
<td>归并排序</td>
</tr>
</tbody>
</table>
<h2>常用数据结构复杂度对比</h2>
<table>
<thead>
<tr>
<th>数据结构</th>
<th>查找平均</th>
<th>查找最坏</th>
<th>插入平均</th>
<th>插入最坏</th>
<th>删除平均</th>
<th>删除最坏</th>
<th>遍历</th>
</tr>
</thead>
<tbody>
<tr>
<td>数组</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>--</td>
</tr>
<tr>
<td>有序数组</td>
<td>O(logn)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td>链表</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>--</td>
</tr>
<tr>
<td>有序链表</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(n)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(n)</td>
</tr>
<tr>
<td>二叉查找树</td>
<td>O(logn)</td>
<td>O(n)</td>
<td>O(logn)</td>
<td>O(n)</td>
<td>O(logn)</td>
<td>O(n)</td>
<td>O(n)</td>
</tr>
<tr>
<td>红黑树</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(n)</td>
</tr>
<tr>
<td>平衡树</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(n)</td>
</tr>
<tr>
<td>二叉堆<br />（优先队列）</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(logn)</td>
<td>O(n)</td>
</tr>
<tr>
<td>哈希表</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(1)</td>
<td>O(n)</td>
</tr>
</tbody>
</table>