We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
数组的本质是把数据存储在计算机内存管理器开辟的连续内存地址中,所以数组的随机访问时间复杂度为O(1),搜索的时间复杂度为O(n),插入删除元素由于平均需要移动半个数组的元素,时间复杂度为O(n)。
链表的本质是每个元素靠指针指向其相邻元素,随机访问时间复杂度因为需要遍历整个链表,所以访问和搜索的时间复杂度为O(n),插入删除元素只需要处理相邻元素的指针指向关系,所以时间复杂度为O(1)。
跳表的本质是在链表的基础上进行升维,加入多级索引,每级索引不再是跳向相邻元素,而是跳跃2^k个元素,其底层实现有多种方式,有BST,AVL等,访问和搜索的时间复杂度为O(logn),增删元素的时间复杂度也是O(logn)。
The text was updated successfully, but these errors were encountered:
No branches or pull requests
数组本质
数组的本质是把数据存储在计算机内存管理器开辟的连续内存地址中,所以数组的随机访问时间复杂度为O(1),搜索的时间复杂度为O(n),插入删除元素由于平均需要移动半个数组的元素,时间复杂度为O(n)。
链表本质
链表的本质是每个元素靠指针指向其相邻元素,随机访问时间复杂度因为需要遍历整个链表,所以访问和搜索的时间复杂度为O(n),插入删除元素只需要处理相邻元素的指针指向关系,所以时间复杂度为O(1)。
跳表本质
跳表的本质是在链表的基础上进行升维,加入多级索引,每级索引不再是跳向相邻元素,而是跳跃2^k个元素,其底层实现有多种方式,有BST,AVL等,访问和搜索的时间复杂度为O(logn),增删元素的时间复杂度也是O(logn)。
The text was updated successfully, but these errors were encountered: