ソートされた配列に数値があるかどうかを調べる関数があります。sは、合計であるxになります。私はこの機能のために大規模な複雑さが何であるかを知りたい。私はそれがO（n）で動くと思うが、私は確信していない。私の機能はO（n）で動作しますか？
機能：
def sumInside(s, x):
# Two indices that will be compared
l = 0
r = len(s) - 1
# Go through the array for the elements
while l < r:
if s[l] + s[r] == x:
return True
elif s[l] + s[r] < x:
l += 1
else:
r -= 1
return False
つのルール：。
最初の質問に対する回答はnです。 1つのループがあり、データ全体を一度繰り返し処理します。
2番目の質問にも簡単に答えます。各ループで比較が行われていますが、これは一定の時間操作です。
全体的に、関数は最悪の場合には線形時間で実行されます - O(n)。
(O(n))でOは、最悪のシナリオにかかる時間を意味します。比較を基本操作として行うと、n要素の入力サイズに対して最悪の場合は2 * nの比較が行われます。したがって、この例では、線形処理時間を持っている（O（n））は、親指の
は "ビッグああ最悪の場合を意味し、" いいえ、それはしていません。ビッグ・オを使って、あなたが望むどのような場合でも（あるいは最善のケースまたは最悪の場合のコンセプトが意味をなさない関数/プロパティについてさえも）推論することができます。 – sepp2k
確かに。 big-Ohは関数の漸近上限を指定し、関数の最悪/最良/平均/または償却された複雑さについては何も言いません。 –
はい、
最悪のシナリオO(n)最悪のケースでは、あなたの要素がn倍となる右端（右にすべての方法をインクリメントしなければならないリットル）、にあります。
最後の部分がO(1)の場合は、最初に試してみてください。 l = 0。
理論的には、平均の場合xは常に中間にあり、それはn/2回の反復をとります。これはO(n)です。
ベスト：O(1)
平均：O(n)
は最悪：O(n)
ありがとうございました！ルールを念頭に置いておきます – tushariyer