Pythonデータ構造とアルゴリズム-あるリストから2つの最も近いが等しくない数を見つける

先に並べ替えて、また...(結局、集計ソートの時間的複雑さはO(nlogn))ソートの幽霊にすぎない.ソートと検索は本当に良い友达です.
基本バージョンを見てみましょう.

from random import randrange
seq = [randrange(10**10) for _ in range(100)]
dd = float('inf')
for x in seq:
    for y in seq:
        if x == y: continue
        d = abs(x-y)
        if dd > d:
            xx, yy, dd = x, y, d
>>> xx, yy
(15743, 15774)

2層のネストは,明らかに2乗レベルの操作である.もちろん握手の問題のように、比較を繰り返す項目はたくさんあります.

for i in range(len(seq)-1):
    for j in range(i+1, len(seq)):
        if i == j or seq[i] == seq[j]:
            continue
        d = abs(seq[i]-seq[j])
        if dd > d:
            x, y, dd = seq[i], seq[j], d

依然として平方レベルの操作です.
まず、並べ替えられたシーケンスを処理するのは比較的容易であることを知っています.すなわち、並べ替えられたシーケンスの中で最も近い2つの数は必然的に隣接していますが、並べ替えは通常線形対数レベル(O(nlogn))の操作であり、1回の並べ替えでは、1労永逸であり、複数回の検索で、

seq.sort()
for i in range(len(seq)-1):
    x, y = seq[i], seq[i+1]
    if x == y: continue
    d = abs(x-y)
    if dd > d:
        xx, yy, d = x, y, d

新しいソリューションの実行時間は線形対数レベルであり,ソート操作が主導する.