图形、树等数据结构如何得出它们的时间复杂性和行为,即使它们是使用列表/数组实现的



>这些数据结构的行为和属性不会影响"更高"数据结构(如图形、二叉树、链表等(的行为吗?例如:数组的访问是O(1)那么这个属性如何影响或考虑二叉树O (log n)的时间复杂度?

O(1)是通过索引访问数组元素的时间复杂度。

可以使用数组作为二叉树的后备存储。这确实会让您为最终按索引进行数组访问的操作提供O(1)时间复杂度,但对于其他事情则不会。

例如,您可以在O(1)中获取树的根元素 - 这只是从位置 0 的数组中检索它。

但是,如果您想找出树中是否存在元素,则可以归结为(一种特殊形式的(二叉搜索,即 O(log n)

另请注意,并非数组上的每个操作都是O(1)的。二叉搜索是O(log n)的,这假设数组是排序的。如果不是,则需要进行线性搜索,即 O(n) .

最新更新