LIS（最長増加部分列）をO(2^N)かけて可視化してみた

本来なら、計算量O(NlogN)で済むところを、数弱の頭でなんとか考えた挙句O(2^N)という最悪の計算量でLISを求め可視化して見ました。

グラフを見ると簡単ですが、実際にアルゴリズムを作るとなると手間がかかりました。

LISとは

LISとはLongest increasing Subsequence の略であり、日本語では最長増加部分列というそうです。

l_n = [51, 4, 11, 8, 41, 90]

という配列があったとします。

この場合のLISは

4 8 41 90
4 11 41 90

の二つになります。

これをmatplotlibを用いてグラフにしてみると、

from matplotlib import pyplot as plt 
n_l = [51, 4, 11, 8, 41, 90] 
fig = plt.figure()
x = [i for i in range(len(n_l))]
y = [int(i) for i in n_l]

plt.scatter(x,y)
plt.xlabel('x')
plt.ylabel('y')
put.imshow()

以下のようになります。

このグラフの中で自身より右側にあり、かつ大きいプロットを辿っていった線のうち一番多くの点を含むものがLISとなります。

今回のl_nにはLISが二つあるので、２つ折れ線グラフができます。

数が増えた場合

例えば、8000個くらいのランダムな数を生成し、n_lにリストとして代入するとします。

import random
n_l = [random.randint(1, 8071) for i in range(8070)]

これをグラフにプロットしてみると、以下のようになります。

fig = plt.figure()
x = [i for i in range(len(n_l))]
y = [int(n_l[i]) for i in range(len(n_l))]
plt.scatter(x,y,s = 1)
plt.xlabel('x')
plt.ylabel('y')

fig.savefig('img_3.jpg',dpi=500)