[baekjoon/Python]4673セルフサービス番号

初志

100がセルフサービス番号かどうかを確認するために、forゲートを通って100に移動しようとします.
=>>時間の無駄

結果コード

1001個のリストを作成し、すべてFalseに設定

12001に移動し、対応する数字(i)の各桁数を加算し、得られた値をTrueに変換します.

は最後に10001まで回転し、エラー値のインデックスを出力します.

時間の複雑さ

時間の複雑さをどのように計算するか分かりません.初めて問題を見て、考える方法より効率しか知らなかった.似ていなければどちらが良いか判断して...時間の複雑さ/メモリの面でアルゴリズムを簡略化するのに役立つ計算方法を整理する.
大まか(liリストn(10001または1000)+(i設定2回)+(n=i n回)
+~~~と計算すると...8-8

li = [ False for i in range(10001)]
for i in range(1,10001):
    n = i
    for j in str(i):
        n += int(j)
    if n<10001: li[n] = True

for i in range(1,10001):
    if not li[i]:  print(i)