複雑さ


複雑さ


これは
  • アルゴリズムの性能を体現する方法である.
  • 2モデル:
  • 時間複雑度:アルゴリズムに必要な演算量
  • 空間複雑度:アルゴリズムに必要なメモリ量
  • は、通常、時間的複雑度および空間的複雑度が取引関係(trade−off)によって確立される.
  • 時間の複雑さ


    時間の複雑さを表す場合はbig-oマーキング法を用いる.

    ビオ記号法


    最速成長を考慮した港湾の標識法

    タイムアウトが1秒の場合:
    Nの範囲時間複雑度N<500 O(N^3)O(N 3)N<2000 O(N^2)O(N^2)N<100000 O(Nlogn)O(Nlogn)N<1000000 O(N)O(N)

    くうかんふくざつさ


    タグ空間の複雑さにもbigoタグ法が用いられる.
  • は、一般に符号化試験において、メモリ使用量が128〜512 MBに制限される.
  • じかんそくていほう

    import time 
    start = time.time() 
    end = time.time() 
    print(end - time)