算法和算法分析
时间复杂度
重要程度：9 分
<div>
<h2>时间复杂度</h2>
<p>时间复杂度是衡量算法效率的重要指标，它表示算法执行所需的时间量级。通常用大O符号表示，忽略掉低阶项和常数因子。</p>
<ul>
<li><strong>O(1)</strong>：常数时间复杂度，表示算法执行所需时间与输入规模无关。</li>
<li><strong>O(n)</strong>：线性时间复杂度，表示算法执行所需时间与输入规模成正比。</li>
<li><strong>O(log n)</strong>：对数时间复杂度，常见于二分查找等算法。</li>
<li><strong>O(n^2)</strong>：平方时间复杂度，常见于嵌套循环。</li>
<li><strong>O(2^n)</strong>：指数时间复杂度，常见于暴力搜索算法。</li>
</ul>
<h3>时间复杂度举例</h3>
<p>考虑以下代码片段：</p>
<pre>
<code>
for (int i = 0; i < n; i++) {
// 执行一些操作
}
</code>
</pre>
<p>上述代码的时间复杂度为<code>O(n)</code>，因为循环会执行n次。</p>
<p>再看一个嵌套循环的例子：</p>
<pre>
<code>
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// 执行一些操作
}
}
</code>
</pre>
<p>上述代码的时间复杂度为<code>O(n^2)</code>，因为内层循环会执行n次，外层循环也会执行n次，总共执行<code>n * n = n^2</code>次。</p>
<p>最后，考虑二分查找算法的时间复杂度：</p>
<pre>
<code>
int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
</code>
</pre>
<p>上述代码的时间复杂度为<code>O(log n)</code>，因为每次迭代数组的规模都会减半。</p>
</div>