my_listN 個の要素を含むPython リストがあるとします。単一の要素は、 を使用してインデックスを付けることができますmy_list[i_1]。ここi_1で、 は目的の要素のインデックスです。my_list[i_1:i_2]ただし、リストの「スライス」が必要な場所では、Python リストi_1にインデックスを作成することもできますi_2。サイズ N のリストをスライスするための Big-O (最悪の場合) 表記法は何ですか?
個人的には、「スライサー」をコーディングしている場合、からi_1を反復しi_2、新しいリストを生成してそれを返し、O(N) を意味しますが、これは Python の方法ですか?
ありがとうございました、
スライスを取得するのは O( i_2 - i_1) です。これは、リストの Python の内部表現が配列であるためi_1ですi_2。
詳細については、Python Time Complexity wiki エントリを参照してください。
必要に応じて、 CPython ソースの実装を確認することもできます。
http://wiki.python.org/moin/TimeComplexityによると
それは O(k) です。ここで、k はスライス サイズです。
サイズ N のリストとサイズ M のスライスの場合、反復は実際には O(N) ではなく O(M) のみです。M はしばしば << N であるため、これは大きな違いになります。
実際、あなたの説明を考えれば、その理由がわかります。0 から i_1 ではなく、i_1 から i_2 まで繰り返し、次に I_1 から i_2 まで繰り返します。