数据结构时间复杂度和频率

时间复杂度是指算法执行耗费时间的度量，是一个算法执行时间与问题规模之间的函数关系。在计算机科学中，数据结构与算法是一对不可分割的伙伴。时间复杂度是评估数据结构与算法性能的重要指标之一，通常用于衡量算法的执行效率，并且可以帮助我们在面对大规模问题时，选择合适的算法和数据结构。

时间复杂度从大体上，可以分为常数时间复杂度、线性时间复杂度、对数时间复杂度、平方时间复杂度、指数时间复杂度五类。时间复杂度的量级可以用O( )来表示，也就是我们常听说的大O符号。这里我们以常见的常数时间复杂度、线性时间复杂度、对数时间复杂度为例进行分析。

常数时间复杂度：

常数时间复杂度是指，算法执行时间不受问题大小影响，也就是在所有数据集大小下，均需要相同的时间执行。如数组元素的访问和赋值（a[0], a[i] = i, a.push back(i)）等，它们的时间复杂度均为O(1)。

线性时间复杂度：

线性时间复杂度是指，算法执行时间与问题规模成直接的线性关系，即当输入的数据量增加一倍时，执行时间也会增加一倍。以数组为例，遍历一个由n个元素构成的数组，时间复杂度为O(n)。如：

```

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

//do something

}

```

这个循环需要执行n次，而我们算复杂度时，取最高次项，其时间复杂度为O(n)。

对数时间复杂度：

对数时间复杂度是指，算法执行时间与问题规模成反比的对数关系，即当输入的数据量增加一倍时，执行时间会增加一定量而不是增加一倍。经常出现在二分策略中，以查找操作为例，时间复杂度为O(log n)。

以上是从时间复杂度的角度分析的，接下来我们从频率角度来了解数据结构时间复杂度的重要性。

频率是指一个算法在实际执行时需要访问计算机中各个层级存储器的次数，可以理解为对不同存储器的读写操作。随着存储器级别的提高，读写操作的速度逐渐变慢。一般来说，主存访问速度快于缓存访问速度，缓存访问速度快于寄存器访问速度。因此，我们在写代码时，应该优先考虑算法对缓存的影响。打好算法的基础之后，优化算法关注的就是访问装载数据所在的内存单元的次数。

常见数据结构中，数组数据结构的时间复杂度对于缓存友好程度比链表更加友好，因为数组是连续存储的。而链表在进行遍历时，每移动一个节点就要重新从内存中装载下一个节点，因此对缓存更不友好。在实际工程中，我们需要结合具体情况选择合适的数据结构，以达到最高的执行效率。