怎样计算查找各种表的某个结点的时间复杂度?O(n)又是什么意思啊啊?

2025-02-24 05:17:11
推荐回答(2个)
回答1:

为了找到第i个结点,链表中需要从头结点开始一个一个向后查找,直到找到第i个结点为止,所以为了找到第i个结点,需要用i-1个程序步,因此,它们的时间复杂度是O(n),而在顺序表中,可以通过下标直接定位到第i个结点,所以只需要1个程序步,因此,它的时间复杂度是O(1)

回答2:

O(n),是指时间复杂度为线性函数增长,比如在顺序表中进行查找,复杂度就是这些。O(1)是复杂度是一个常数。