[WEEK 19]Pythonアルゴリズムインタビュー

メモリを順番に割り当てるアレイとは異なり、構造体は実際には唯一の複合材料であり、メモリの任意の領域に任意のサイズで割り当てることができます.
Pythonで構造体と同じ形状を定義するには、名前tupleを使用する必要があります.

リスト計算

Pythonはmap、filterなどの関数型機能をサポートし、lambda式もサポートしています.

list(map(lambda x: x + 10, [1, 2, 3]))

リスト計算は、既存のリストに基づいて新しいリストを生成する構文です.

[n * 2 for n in range(1, 10 + 1) if n % 2 == 1]

enumerate

列挙()は、インデックスを含む列挙オブジェクトに順序付きデータ型(list、set、tupleなど)を返す「リスト」を表す関数です.

arr = [1, 3, 5, 7, 2, 4, 6, 8]
list(enumerate(arr))

データ型

big−oは,入力値が大きくなるとアルゴリズムの実行時間(時間的複雑度)と空間的要件(空間的複雑度)がどのように増加するかを分類するために用いられる.
bigoは,漸近実行時間(漸近実行時間:入力値が無限大を指す場合の関数の上限)を表すときに最もよく用いられる数学的表現である.
漸近実行時間は時間の複雑さといえる.
時間複雑度(time complexity)とは、あるアルゴリズムを実行するのに要する時間を記述する計算複雑度(computer complexity)である.
比奥で時間複雑度を表す場合,最高次港湾を表し,定数項を無視する.
O(1):定数時間を持つアルゴリズムは,入力値がどんなに大きくても実行時間が固定される.
O(logn):実行時間は入力値の影響を受けます.しかし,ログは大きな入力値の影響を受けず,一般nのサイズにも非常に堅牢である.代表的なのはバイナリ検索です.
O(n):実行時間は入力値の影響を受け,アルゴリズムの実行に要する時間は入力値に比例する.このアルゴリズムを線形時間アルゴリズムと呼ぶ.ソートされていないリストで、最も値が最も高い場合も同様です.この値を見つけるには、少なくとも1回、すべての入力値をチェックする必要があります.
O(n logn):集計ソートを含むほとんどの効率的なソートアルゴリズムがそうである.少なくともすべての数を1回以上比較する比較ベースのソートアルゴリズムは,いくら良いアルゴリズムでもO(n logn)より速くはならない.
O(n^2):Bubbleソートに類似した非効率ソートアルゴリズム.
O(2^n):フィボナッチ数を再帰的に計算するアルゴリズム.
O(n!): 外板元問題をBrook Forceに変換したとき、そうでした.
アルゴリズムは往々にして「時間と空間の交換」関係である.
実行時間の速いアルゴリズムは空間を占有し、空間の小さいアルゴリズムは実行時間が遅い.
bigoマーキング法は、所定(最適/最悪/平均)の場合の実行時間の上限を表す.