1.1 数据结构的基本概念
<strong>时间复杂度与空间复杂度</strong>
重要程度：9 分
<h2>1.1 数据结构的基本概念</h2>
<h3>时间复杂度与空间复杂度</h3>
<p><strong>时间复杂度：</strong> 时间复杂度是算法效率的一种度量方式，它反映了程序执行时间随输入规模增长的趋势。通常用大O符号（O）来表示。时间复杂度主要关注的是算法中基本操作的执行次数的增长率。</p>
<p><strong>空间复杂度：</strong> 空间复杂度指的是算法在运行过程中所需的最大存储空间量。这包括了输入数据所占的空间、辅助变量等额外空间。同样地，我们也使用大O符号来描述空间复杂度。</p>
<h4>示例分析</h4>
<p><strong>时间复杂度示例：</strong></p>
<code>
// 示例代码：求一个数组中所有元素之和
int sum = 0;
for (int i = 0; i < n; i++) {
sum += array[i];
}
</code>
<p>在这个例子中，循环体被执行了n次，因此其时间复杂度为O(n)。</p>
<p><strong>空间复杂度示例：</strong></p>
<code>
// 示例代码：创建一个长度为n的新数组，并复制原数组的内容到新数组
int[] newArray = new int[n]; // 创建新数组
for (int i = 0; i < n; i++) {
newArray[i] = oldArray[i];
}
</code>
<p>此段代码除了原有的oldArray外，还额外申请了一个大小为n的新数组newArray，所以该算法的空间复杂度为O(n)。</p>
<h4>练习题</h4>
<p>考虑以下函数，计算其时间复杂度和空间复杂度：</p>
<code>
void func(int n) {
int count = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
count++;
}
}
cout << "Count: " << count;
}
</code>
<p>答案解析：</p>
<ul>
<li>时间复杂度：内层循环执行n次，外层循环也执行n次，总共执行\(n * n = n^2\)次。因此，时间复杂度为O(\(n^2\))。</li>
<li>空间复杂度：除了参数n之外，只使用了一个整型变量count作为计数器，故额外使用的空间不依赖于n的大小，是一个常数。因此，空间复杂度为O(1)。</li>
</ul>
这段HTML文本简要介绍了《数据结构导论》第一章中的时间复杂度与空间复杂度的概念，并通过具体例子加以说明，最后提供了一个简单的练习题及解答帮助理解这两个概念。