紅色閃電：探究跳表的時(shí)間復(fù)雜度

跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，可以用來(lái)快速定位、插入、刪除數(shù)據(jù)。跳表的實(shí)現(xiàn)思想簡(jiǎn)單而獨(dú)特，通過(guò)“跳躍式訪問(wèn)”的方式，快速訪問(wèn)到需要的元素，從而達(dá)到O(log n)的時(shí)間復(fù)雜度。本文主要介紹跳表的實(shí)現(xiàn)原理以及時(shí)間復(fù)雜度的探究。

跳表的實(shí)現(xiàn)

跳表的結(jié)構(gòu)是由多個(gè)鏈表組成的，每個(gè)鏈表級(jí)別越高，節(jié)點(diǎn)數(shù)越少、步長(zhǎng)越長(zhǎng)。圖一展示了一張具有4個(gè)級(jí)別的跳表，在該跳表中，每個(gè)節(jié)點(diǎn)都是由一個(gè)值和連向它的指針組成的。


圖一 跳表結(jié)構(gòu)示意圖

跳表的查找操作是從最頂層的鏈表開(kāi)始查找，如果該節(jié)點(diǎn)的值小于目標(biāo)值，則跳到下一層查找，直到找到大于或等于目標(biāo)值的節(jié)點(diǎn)或者最底層鏈表。如果找到了大于或等于目標(biāo)值的節(jié)點(diǎn)，則返回該節(jié)點(diǎn)。如果查找完所有鏈表都沒(méi)有找到目標(biāo)值，則返回空。

代碼實(shí)現(xiàn)：

public class SkipList {
    private skipListNode head;
    private int level;
    public SkipList() {
        head = new SkipListNode(null, null, 0);
        level = 0;
    }
    public void insert(Integer value) {
        int newLevel = getRandomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i 
                SkipListNode newHead = new SkipListNode(null, null, i);
                newHead.down = head;
                head = newHead;
            }
            level = newLevel;
        }
        SkipListNode cur = head;
        SkipListNode[] update = new SkipListNode[level + 1];
        for (int i = level; i >= 0; i--) {
            while (cur.right != null && cur.right.value 
                cur = cur.right;
            }
            update[i] = cur;
            cur = cur.down;
        }

        SkipListNode node = new SkipListNode(value, null, newLevel);

        for (int i = 0; i 
            node.right = update[i].right;
            update[i].right = node;
            node.down = (i 
            node = node.down;
        }
    }

    public boolean delete(Integer value) {
        SkipListNode cur = head;
        SkipListNode[] update = new SkipListNode[level + 1];

        for (int i = level; i >= 0; i--) {
            while (cur.right != null && cur.right.value 
                cur = cur.right;
            }
            update[i] = cur;
            cur = cur.down;
        }

        if (update[0].right != null && update[0].right.value.equals(value)) {
            SkipListNode deletedNode = update[0].right;
            for (int i = 0; i 
                if (update[i].right == deletedNode) {
                    update[i].right = deletedNode.right;
                } else {
                    break;
                }
            }
            return true;
        } else {
            return false;
        }
    }
    public SkipListNode find(Integer value) {
        SkipListNode cur = head;
        for (int i = level; i >= 0; i--) {
            while (cur.right != null && cur.right.value 
                cur = cur.right;
            }
            if (cur.right != null && cur.right.value.equals(value)) {
                return cur.right;
            }
            cur = cur.down;
        }
        return null;
    }

    private int getRandomLevel() {
        int level = 0;
        while (Math.random() 
            level++;
        }
        return level;
    }

    private class SkipListNode {
        private Integer value;
        private SkipListNode right;
        private SkipListNode down;
        public SkipListNode(Integer value, SkipListNode right, int level) {
            this.value = value;
            this.right = right;
            this.down = (level > 0) ? new SkipListNode(value, right, level - 1) : null;
        }
    }
}

跳表的時(shí)間復(fù)雜度

對(duì)于一個(gè)有n個(gè)元素、k個(gè)層次的跳表，查找的時(shí)間復(fù)雜度為O(log n)，插入和刪除的時(shí)間復(fù)雜度也為O(log n)。

比較一下跳表和傳統(tǒng)鏈表的時(shí)間復(fù)雜度：

| 操作 | 平均情況 | 最壞情況 |

| — | — | — |

| 跳表查找 | O(log n) | O(n) |

| 鏈表查找 | O(n) | O(n) |

| 跳表插入 | O(log n) | O(n) |

| 鏈表插入 | O(1) | O(n) |

| 跳表刪除 | O(log n) | O(n) |

| 鏈表刪除 | O(1) | O(n) |

從上表可得出，跳表在查找操作上的時(shí)間復(fù)雜度比傳統(tǒng)鏈表低得多，而插入和刪除操作的時(shí)間復(fù)雜度差距不大。因此，跳表適合插入、刪除操作不頻繁，以查找操作為主的場(chǎng)景。

總結(jié)

跳表是一種高效、靈活的數(shù)據(jù)結(jié)構(gòu)，在快速查找、插入、刪除數(shù)據(jù)方面具有很好的優(yōu)勢(shì)。本文解釋了跳表的實(shí)現(xiàn)原理和時(shí)間復(fù)雜度，并提供了一份跳表的Java實(shí)現(xiàn)代碼。如果您在工作中需要訪問(wèn)大量數(shù)據(jù)，而且需要快速定位數(shù)據(jù)，那么跳表可能是一種不錯(cuò)的選擇。

成都網(wǎng)站建設(shè)選創(chuàng)新互聯(lián)(?:028-86922220),專業(yè)從事成都網(wǎng)站制作設(shè)計(jì),高端小程序APP定制開(kāi)發(fā),成都網(wǎng)絡(luò)營(yíng)銷推廣等一站式服務(wù)。

網(wǎng)站欄目：紅色閃電探究跳表的時(shí)間復(fù)雜度（redis跳表時(shí)間復(fù)雜度）
轉(zhuǎn)載源于：http://uogjgqi.cn/article/dhgsiej.html