Skip to content

删除链表中重复的结点 #830

@lllong33

Description

@lllong33

如果进行 N 次操作,那么大约需要操作节点的次数为 N-1+N=2N-1,其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数,N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2,因此该算法的平均时间复杂度为 O(1)。

O(1) 和 O(N) 能理解 但 2N-1, N ~ 2 怎么理解?

Activity

wangpeipei90

wangpeipei90 commented on Dec 11, 2019

@wangpeipei90

(2n-1)/n 约等于2,O(2)表示常数级复杂度,也就是O(1)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

      Development

      No branches or pull requests

        Participants

        @wangpeipei90@lllong33@CyC2018

        Issue actions

          删除链表中重复的结点 · Issue #830 · CyC2018/CS-Notes