[アルゴリズム]計算アルゴリズムの複雑 - アルゴリズムの複雑さ

[アルゴリズム]計算アルゴリズムの複雑 – アルゴリズムの複雑さ

7月 23, 2014 nguyenvanquan7826 アルゴリズム 10 回答

コンテンツ
アルゴリズムを分析する必要
 プログラムの実行時間
 複雑性およびアルゴリズムの増加率
 計算アルゴリズムの複雑
 再帰方程式ソルバー

更新日 28/05/2014 – もっと目に見えるで提示スペルや数式を修正.
アルゴリズムを取り巻く多くの問題があります。, 特に複雑なアルゴリズム. この記事では、問題を配置します, 関連する概念およびアルゴリズムをチェックする複雑さを示す.
カリキュラムの解析アルゴリズムで参照記事 - CTU

私. 解析アルゴリズムの必要性

問題を解決しながら、我々は、多くの異なるアルゴリズムを持つことができ, 問題は、良いアルゴリズムを選択するためのアルゴリズムを評価する必要がある (最も). 通常、私たちは以下の基準に基づいて行われます:
1. アルゴリズム正しく.
2. 簡易アルゴリズム.
3. このアルゴリズムは、すぐに実装.

リクエストにより (1), アルゴリズムの正しさをチェックするために、我々は、データサンプルの数の実装のためにそれとアルゴリズムをインストールすることができ、得られた結果は、既知の結果と比較され. 実際には、これを行う方法がわからないアルゴリズムが正しく、すべてのデータで、我々は試してみましたが、特定のデータのために間違ったことができるので、. そして、この発見アルゴリズムを行う唯一の方法は間違って証明が、それは真実ではない. アルゴリズムの正しさを数学によって証明されなければならない. もちろん、これは単純ではない、と私たちはここで言及しません.
我々は数回使用するプログラムを書くとき、E Y uが必要 (2) 最も重要である. 私たちは、すぐに結果を得るためのプログラムを書くのは簡単なアルゴリズムを必要とする, これらはほんの数回のみ使用されるため、プログラムの継続時間は、とにかくプログラムを推進されていない.
プログラムが何度も使用されるときには、それは時間を節約するプログラムの実装は非常に大きなデータ入力要求を実行するために必要なプログラムのために特に非常に重要である必要 (3) 慎重に考慮されます. 私は、アルゴリズムの効果的な実行時間を呼び出す.

二. プログラム期間

アルゴリズムの効果的な実行時間を決定する方法は、それをプログラムし、選択した入力のセットを決定するためにコンピュータ上で動作の実行時間を測定している. 実行時間は、アルゴリズムにも依存するだけでなく、コンピュータ命令のセットに応じて, コンピュータの品質とプログラミングのもの. 実行が選択されるデータの特定の組に良いように調整することができ. この障害を克服するために, コンピュータ科学者は、アルゴリズムの性能の基本的な指標として、アクセス時間の複雑さを受け入れている. 長期有効性は、この測定を言及し、特に最悪の場合の時間計算のためになる.
プログラムの期間.
入力サイズの関数でプログラムを作成するための時間, 記号T(N) ここで、nはサイズである (マグニチュード) 上のデータ. n個の数の和は、実行時間Tである(N) cは定数である= Cnは. プログラムの継続時間は、非負関数である, すなわちT(N) ≥ 0 すべてのn≥ 0.
対策実行時間の単位.
Tの単位(N) いつもの時間のような時間の測定単位ではありません, 瞬間… 通常、理想的なコンピュータで実行されるコマンドの数によって決定される. 我々は、プログラムの実行時間がTであると言うとき(N) = Cnが、それは彼がCNプログラム実行ディレクティブが必要であることを意味します.
最悪の場合には実行時間.
一般に、プログラムの継続時間だけでなく、大きさに依存するだけでなく、データの性質に依存. すなわち、同じ大きさのデータが、異なる場合があり、プログラムの継続期間である. 昇順に配置されたこのようなプログラムの整数, 私たちは何シーケンス順序入力されていないときよりも、他の整然としたシーケンス実行時間に入ったとき, 我々は昇順を入力したとき、または、実行時間は、私たちが降順でシーケンスのためにそこにいたときとは異なります. そう頻繁に私達は、Tを参照してください。(N) 入力サイズn上の最悪の場合には、プログラムの継続期間, すなわち: T(N) 同じ大きさnのすべてのデータのためのプログラムを実施するための最大時間である.

三. アルゴリズムの率の増加と複雑

速度が増加する
私たちは、非負関数Tと言う(N) マージンを大きく (成長速度) F(N) もし $\exists \ C, N_{0} \ | \ T(n) \leq Cf(n), \forall \ n \geq N_{0}.$
我々はそれを証明することができます 非負関数T用(N) すべての, 私はfの増加率を常に見つける(N) その.
仮定する $T(0) = 1,\ T(1) = 4$ および一般: $T(n) = (n+1)^{2}$ .
場所 $\ N_{0} = 1, \ C = 4$ その後、すべてのnに対して≥1我々は簡単にそれを証明する:
$T(n) = (n+1)^{2} \leqslant 4n^{2}, \forall \ n \geq 1$ , の増加率、すなわち $\ T(n) = n^{2}$ .
機能の増加率 $\ T(n) = 3n^3 + 2n^2 = n^3$ .
確かに, 与える $\ N_{0} = 0, \ C = 5$ それはあることを証明するのは簡単です $\forall n \geq 0 \Rightarrow 3n^3 + 2n^2 \leqslant 5n^{3}$
アルゴリズムの複雑さの概念
私たちはそれぞれのアルゴリズムの実行時間との2 P1およびP2があるとします:
$\begin{cases} T1(n) = 100n^2 & \text{ ty suat tang la } n^2 \\ T2(n) = 5n^3 & \text{ty suat tang la } n^3 \end{cases}$
このアルゴリズムは、より速く実行されます? 答えは、上のデータのサイズに依存する. nの < 20 より高速のP1、P2 (T2<T1), 100N未満の5N ^ 3 ^ 2の係数の係数を (5<100). しかし、時のn > 20 5N ^ 3の100N ^ 2より小さい指数の指数によって他方では (2<3). ここでは、ケースのnにのみ関心がある>20 n個のときのため<20 P1とP2の両方の実行時間が大きくなく、T1とT2との間の差は無視できる.
そのように、論理的に、我々は、成長速度は、実行時ではなく、プログラム自体の持続時間の関数で考える.
関数Tのために(N), T(N) と呼ばれる複雑さのF(N) もし $\exists \ C, N_{0} \ | \ T(n) \leq Cf(n), \forall \ n \geq N_{0}.$ (すなわちT(N) マージンの増加がFだった(N)) とOで示される(F(N)). (“Fのプロット(N)”)
$T(n)= (n+1)^2$ 成長速度がでnは^ 2べき $T(n) = O(n^2)$
注目: ザ·(C.f(N))= O(F(N)) そしてCは定数である. 特別O(℃) = O(1)

言い換えると、アルゴリズムの計算の複雑さは、時間上の機能ブロックの関数である. そのため無し感覚上のファンクションブロックの死の定数Cの、私たちはとても複雑な関数は、後に一般的な形を表し、無視することができます:
$logn, n, n^2, n^3, 2^n, n!m n^n$ .
最後の3つの関数は、指数関数形と呼ばれている, 多項式と呼ばれる別の機能. 複雑さが多項式である場合、それは許容可能であること、リアルタイムアルゴリズムは、実行するためにインストールすることができ, アルゴリズムは、指数関数的複雑性を有するが、それらはアルゴリズムを改善する方法を見つけなければならない.
注目: LOGNにそのベースので気にしない $log_{a}n = log_{a}b.log_{b}n = log_{b}n, b > 0$ (ルールドロップ係数は、後に言及します)
我々は、プログラムの実行時間の効果に話したいということであるときには、アルゴリズムの複雑さになるので、プログラムの実行時間は、アルゴリズムの複雑さを定義することであるかを判断することができる.

4. HOW COMPLEXITYアルゴリズム

任意のアルゴリズムの計算の複雑さは、単純な問題ではありません. しかし、我々はいくつかの原則に従うことができます:
ルールは、定数与える
プログラムPのセグメント持続時間T場合(N) = O(c1.f(N)) c1は正の定数である
それは計算の複雑さを持つプログラムセグメントがOで考慮することができる(F(N)).
共産ルール – マックスを得る
T1の場合(N) とT2(N) 二つのセグメントのP1とP2のプログラムの実行時間; とT1(N)= O(F(N)), T2(N)= O(グラム(N)) 別の後のプログラムの第二段階の持続時間はTである(N)= O(マックス(F(N),グラム(N)))
最高経営責任者（CEO:
割り当てのX:= 15は、一定時間またはOを取る(1), データコマンドreadlnを読む(X) 一定の時間がかかるか、O(1).
だから、順序で両方のコマンドをする時間はO(マックス(1,1))= O(1)
CAMの
T1の場合(N) とT2(N) 2つのプログラムセグメントP1va P2とT1の実行時間(N) = O(F(N)), T2(N) = O(グラム(N)) Tネストされているプログラムセグメントの第二段階の期間(N) = O(F(N).グラム(N))
プログラムを解析するための一般的なルール
– 各割り当ての実行時間, READ, WRITEのO(1).
– 一連のコマンドの実行時間は、公共のルールによって決定されます. したがって、この時間は、最長のコマンド文字列内の特定のコマンドを実装する時間です.
– 実行時間は最大でTHENまたはELSEの後に次のコマンドを実行し、時間の条件をチェックすると時間構造である. 多くの場合、時間はO試験条件である(1).
– ループの実行時間が合計である (すべての繰り返しで) ループ本体の期間. ループ本体の持続時間は、ループの長さを変更しない場合は、時間ループ本体を実行する反復回数の積である.
最高経営責任者（CEO: 手続き配置」泡沫」の期間を計算

procedure Bubble (var a: array[1..n] of integer);
var i,j,temp: integer;
begin
	for i:=1 to n-1 do					{1}
		for j:=n downto i+1 do				{2}
			if a[j-1]>a[j] then			{3}
			begin
				temp:=a[j-1];			{4}
				a[j-1]:=a[j];			{5}
				a[j]:=temp; 			{6}
			end;
end;

バブルソートアルゴリズムに, 我々はより詳細に説明します 2. ここにある, 我々は、アルゴリズムの複雑さにのみ関心がある.
私は、プログラム全体にリピートオーダーで構成されていまし {1}, 順番にケージ {1} コマンド {2}, 順番にケージ {2} コマンド {3} 順番に統合 {3} た 3 順番 {4}, {5} と {6}. 我々は、内側から順に、複雑な計算を行います.
最初, すべての3つの割り当て {4}, {5} と {6} それぞれがOをとり(1) 時間, 比較[jは、1] > ザ·[J] またOをとり(1) 時間, したがって、コマンド {3} Oをとり(1) 時間. ループ {2} 実行する (N-I) 時間, 各O(1) そうループ {2} Oをとり((N-I).1) = O(N-I).ループ {1} 私はから実行して繰り返し 1 ループのn-1個の実行時間まで {1} また、アルゴリズムの複雑さである:
$T(n) = \sum_{i=1}^{n-1}(n-i) = \frac{n.(n-1)}{2} = O(n^2)$
注目: ループの場合、反復回数を決定することができない、我々は、最悪の場合には、反復回数を取る必要.
検索シーケンシャル. 検索機能は、n個の整数aを持つ配列と整数xを受信する, 要素が存在する場合、関数はTRUE論理値を返します。[で] = X, 逆関数はFALSEを返します.
検索アルゴリズムは、順次ターンは配列aの要素とXを比較している, から始まる[1], 存在する場合は、[で] = Xが、その後停止し、TRUEを返します, 機能の他のすべての要素であれば、その逆、それはFALSE Xを返します。.

FUNCTION Search(a:ARRAY[1..n] OF Integer;x:Integer):Boolean;
VAR i:Integer;
	Found:Boolean;
BEGIN
	i:=1; 											{1}
	Found:=FALSE; 									{2}
	WHILE(i<=n) AND (not Found) DO					{3}
		IF A[i]=X THEN Found:=TRUE ELSE i:=i+1; 	{4}
	Search:=Found; 									{5}
END;

私は、コマンドを参照してください {1}, {2}, {3} と {5} 織り方, したがって、検索機能の複雑さは最も複雑である 4 このコマンドは、. 3受注のを見て簡単に {1}, {2} と {5} 複雑Oがあります(1) したがって、検索機能の複雑さは、コマンドの複雑さである {3}. 順番にケージ {3} コマンド {4}. オーダー {4} 複雑さO(1). 最悪の場合に (そのすべての要素が異なるXです) ループ {3} 行わn回, だから我々は、Tを持っている(N) = O(N).
サブルーチンを呼び出すことができるプログラムの複雑さは、再帰的ではありません
我々はありません再帰的なサブルーチンを使用してプログラムを持っている場合, プログラムの実行時間を算出する, まず、他のサブルーチンを呼び出すことはありませんプログラムの実行時間を計算する. その後、我々は、プログラムの実行時間を計算するには、単にそれらの実行時間を計算するサブルーチンを呼び出す. 我々は評価したすべてのサブルーチン呼び出しの実行時間後の各サブルーチンの実行時間を評価するプロセスを続行. 最後に、メインプログラムのための時間を計算する.
私たちは次の図で一緒に呼び出されたプログラムのシステムがあるとします:
dequy
サブルーチンと呼ばれる第二のプログラムは、BとCである, Bプログラムサブルーチン二つB1とB2と呼ばれている, B1プログラムサブルーチンは2 B11とB12と呼ばれている.
Aの実行時間を算出する, これは、以下の手順に従って計算される:
1. Cの期間を計算, B2, B11とB12. プログラムは、すべてのサブルーチンを呼び出すことはありませんので.
2. B1の持続時間を計算する. B11とB12の実行時間がステップで算出されたことをB1とB12 B11呼び出し以降 1.
3. Bにかかる時間を計算します. B1の実行時間ステップで計算されたためと呼ばれるB1とB2 B 2 及びB2の期間はステップにおいて算出された 1.
4. の持続時間を計算する. 呼B及びC Bの持続時間は、ステップで算出されたため 3 及びCの期間はステップで算出された 1.
次のように私たちは、バブルソートプログラムを書き換えることができます: まず、お互いにスワップスワップ2つの要素を実行するための手順を書く, その後手続きバブル, 必要なときに、私たちは、この手順スワップを呼び出します.

procedure Swap (var x, y: integer);
var temp: integer;
begin
	temp := x;
	x := y;
	y := temp;
end;
procedure Bubble (var a: array[1..n] of integer);
var i,j :integer;
begin
	for i:=1 to n-1 do								{1}
		for j:=n downto i+1 do						{2}
			if a[j-1]>a[j] then
				Swap(a[j-1], a[j]);					{3}
end;

上の書面で, サブルーチンスワップと呼ばれるバブルプログラム, したがって、バブルの実行時間を算出する, まずスワップの実行時間を計算する必要が. O·スワップの実行時間を簡単に確認することができ(1) それだけで含まれているため、 3 割り当て. バブル, コマンド {3} スワップは、Oのみの費用を呼び出す必要があります(1), コマンド {2} のn-iの倍の実装, それぞれがOをとり(1) Oかかるはず(N-I). オーダー {1} 実施のn-1べき:
$T(n) = \sum_{i=1}^{n-1}(n-i) = \frac{n.(n-1)}{2} = O(n^2)$
再帰プログラムの分析
サブルーチン再帰的に呼び出すことができるプログラムを使用, あなただけの提示として再帰的なプログラムは、自分自身を呼び出しますので、計算を適用し、ある方法の場合することはできません, プログラムAの実行時間を算出する, 我々は、プログラムの実行時間および終了することができない悪循環を計算しなければならない.
再帰的なプログラムと, 我々は最初の再帰方程式を確立すべきである, その後再帰方程式, 再帰式は再帰プログラムの実行時間となります.
設立再帰方程式
再帰的な式は、Tの関係式で表される(N) とT(へ), ここで、T(N) 入力サイズnのプログラムの継続期間, T(へ) 入力データサイズが番組の時間実装をk, kは < N. 再帰方程式を確立する, これは、再帰的なプログラムに基づくものでなければならない. 通常、再帰的なプログラムは、問題のサイズnを解決するために, 少なくとも一つのケースは、問題のサイズkを解決するための具体的なnの再帰呼び出しで停止している必要があります (K0プログラムはGiai_thua再帰的に呼び出す必要があります(-1), これは再帰呼び出しTかかります(-1), 再帰呼び出しの結果の後に, プログラムは、nで結果を乗算しGiai_thuaを割り当てる必要があります. 乗算と割り当てを実行するための時間が定数C2です. だから我々は持っている
$T(n) = \begin{cases} C1 & n=0 \\ F(T(n-1)) + C2 & n>0 \end{cases}$
これは、再帰プログラムの実行時間を計算する再帰的な式であるGiai_thua.
私たちは次のように手順がアウトラインをマージソート考える:

FUNCTION MergeSort (L:List; n:Integer):List;
VAR L1,L2:List;
BEGIN
	IF n=1 THEN RETURN(L)
	ELSE
	BEGIN
		Chia đôi L thành L1 và L2, với độ dài n/2;
		RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2)));
	END;
END;

例えば、リストLをソートすることで構成されてい 8 要素 7, 4, 8, 9, 3, 1, 6, 2 次のように我々は、マージソートのモデルが示されている:

マージ関数は、長さnのリストを受け取り、ソートされたリストを返す. マージ手順は、2つのリストL1とL2は、注文のn個の要素のリストを取得するために、長さのn / 2の各々は、それらを一緒に混合するリストしようとしているかかる. アルゴリズムの詳細をマージは後ほど説明します, 私たちは、長さのリストをマージする時間がN / 2がOであることに注意してください(N). Tを呼び出し(N) かかる時間はT次に、n個の要素のリストをマージ(π/ 2) リストマージソートの期間N / 2要素. ときに、長さL 1 (N = 1) プログラムはリターンです行うには一つだけである(L), それはOを取る(1) = C1時. n個の場合 > 1, 二回、長さN / 2の再帰呼び出しMerSort L1およびL2を実行するためのプログラムは、そのように二回再帰を呼び出すための時間は2Tです(π/ 2). また、それは2つを一緒に混合することによって半分にリストLの分割に時間がかかり、結果リスト (行く). これは、リストを分割およびマージする時間がOであると定義される(N) = C2nの. だから我々は、次の再帰式を持っている:
$T(n) = \begin{cases} C1 & n=1 \\ 2T(\frac{n}{2}) + C2.n & n>1 \end{cases}$

ザ·. 再帰方程式ソルバー

取得するメソッド:
すべてのTを置き換えるために再帰を使用して(M) Mと<mが1になるまでPTの右側のn.
最高経営責任者（CEO: 再帰方程式ソルバー:
$T(n) = \begin{cases} C1 & n=1 \\ 2T(\frac{n}{2}) + C2.n & n>1 \end{cases}$

私が持っている:
$T(n) = 2T(\frac{n}{2}) + C2.n$
$=2[2T(\frac{n}{2})+ C2.\frac{n}{2}] + C2.n = 4T(\frac{n}{4}) + 2.C2.n$
$=4[2T(\frac{n}{8})+ C2.\frac{n}{4}] + C2.n = 8T(\frac{n}{8}) + 3.C2.n$
= …
$=2^{i}.T(\frac{n}{2^{i}}) + i.C2.n$
リーグの歴史 $n=2^k$ そして最後に、我々はI = Jを持っている.
$\Rightarrow T(n) = 2^{k}T(1) + kC2n$
そこ:
$n=2^k \Rightarrow k = logn, T(1) = C1\\ \Rightarrow T(n) = 2^{k}T(1) + kC2n\\ \Rightarrow T(n) = n.C1 + C2.n.logn\\ \Rightarrow T(n) = O(n.logn)$

一般的方法
問題児と各問題サイズN / Bに問題を分割. そして問題まで、すべてのそのような共有が解決するのに十分に小さい (再帰的な). この方法を使用した後に、再帰的な方程式のことが示されている:
$T(n) = \begin{cases} C1 & n=1 \\ aT(\frac{n}{b}) + C2.n & n>1 \end{cases}$
私が持っている:
T(N) = C1 n = 1の場合
nの>1 我々は持っています:
$ラテックスT(N) = 開始{ケース} ザ·(N) & \テキスト{ もし } ザ· < b \\ O(n.log(n)) & \text{ if } a=b \\ O(n^{loga}) & \text{ if } a > bはエンド{ケース}$

カリキュラム解析アルゴリズムの中で参照記事 – CTU

あなたは好きかもしれません:

10 上の回答 [アルゴリズム]計算アルゴリズムの複雑 – アルゴリズムの複雑さ

ファム・ヴァン・ダット 言う:

3月 13, 2016 アット 4:16 午後

記事のラテックス残念LAH aの最後の段落?

返信
1. ティエンヴ 言う:
  
  11月 7, 2017 アット 1:51 午後
  
  どうやらla` VのEM
  
  返信
Khueヴ 言う:

3月 11, 2018 アット 12:24 アム

このアルゴリズムはずっと先生であるようにあなたが行う場合 ?
のために(長い長いI = 0;で>パイル[で];
のために(長い長いJ = 0;J<= I;J )
{
もし(パイル[で]<雪[J])
{
雪[J] -=杭[で];
合計+ =杭[で];
}
ほかに
{
合計+ =雪[J];
雪[J] = 0;
}
}
COUT<<合計<<" ";
}

返信
1. nguyenvanquan7826 言う:
  
  3月 15, 2018 アット 10:23 アム
  
  ザ·(N ^ 2) NHE.
  
  返信
ngocthach 言う:

5月 15, 2018 アット 2:40 午後

私a..Help提出されたこの貴重であるものの複雑さのCt
int型Tohop(int型のn, int型のK){
もし(K == 0||K == N)
リターン 1;
リターン( 跳ねる(N-1、K-1)+跳ねる(N-1、K)

返信
ケント 言う:

5月 29, 2018 アット 11:07 アム

私はこのプログラムセグメントの複雑さを聞いてみようどのくらいです先生:
のために (I = 0; で<N; 私 )
K ++;
のために (I = 0; で<N; 私 )
のために (J = 0; J<N; J )
K ++;

返信
ニャチャン 言う:

5月 3, 2019 アット 8:23 午後

私はすべての患者の先生カバレッジCの雑誌のためにこれを頼みます
パッケージdoannhom;

輸入java.util.Arrays;

パブリッククラスConvertBTtoBST {
パブリック静的クラスノード{
intデータ;
ノードの左;
ノードを右;

公共ノード(intデータ){
this.data =データ;
this.left = nullを;
this.right = nullを;
}
}
公共のノードのルート;

int型[] treeArray;
int型のインデックス= 0;

公共ConvertBTtoBST(){
ルート= nullを;
}
公共ノードinsertLevelOrder(int型[] ARR, ノードのルート, int型の私){
もし (私は終わります) {
リターンヌル;
}
int型ミッド= (開始 + より) / 2;
Node node = new Node(treeArray[ミッド]);
node.left = createBST(開始, ミッド – 1);
node.right = createBST(ミッド + 1, より);
リターン・ノード;
}
公共のボイドinorderTraversal(Node node) {

もし(ルート==ヌル){
のSystem.out.println(“ツリーは空です”);
リターン;
}
ほかに {

もし(node.left!= nullを)
inorderTraversal(node.left);
System.out.print(node.data + ” “);
もし(node.right!= nullを)
inorderTraversal(node.right);

}
}

公共の静的な無効メイン(文字列[] 引数) {

ConvertBTtoBST BT =新しいConvertBTtoBST();
int型ARR[] = { 10, 2, 7,8, 4 };
bt.root = bt.insertLevelOrder(ARR, bt.root, 0);
bt.inOrder(bt.root);
ノードBST = bt.convertBTBST(bt.root);
のSystem.out.println(“\結果のバイナリ検索ツリーのnInorder表現: “);
bt.inorderTraversal(BST);
}
}

返信
ペイント 言う:

12月 14, 2019 アット 10:39 アム

敬礼
私はまだ非常によくあなたが説明することができますどのように理解していない=何とかより理解しやすいではありません
場合と仮定 1 アルゴリズムの場合 (N <= 0) 複雑な原料いただけません

返信
グエンティエンアン 言う:

4月 15, 2020 アット 10:05 アム

1. のために (i = 1;で<= N;私 )
2. のために (u = 1;で<= M;++)
3. のために (v = 1;で<= N;v ++)
4. //コマンド
5. のために (j = 1;J<= X;J )
6. のために (k = 1;へ<Z =;K ++)
7. //コマンド
投稿 1 いくら
1. s = 1; P = 1;
2. のために (i = 1から;で<= N;私 ) {
3. p = p * X / で;
4. S = Sで + P;
5. }
投稿 2 bn結果so a

一連の整数aに異なる倍精度数を含む. 最初の要素の位置規則は 0. 要素の値がシーケンスaまたは指定されたkのどこにあるかを検索します -1 kに等しい要素がない場合.
TIMKIEM.INPファイルからの入力の形式は次のとおりです。:
– 最初の行には整数nとkが含まれています
– 2行目にn個の数値が含まれています
出力ファイルTIMKIEM.OUTの形式は次のとおりです。: 数列におけるkの位置.
提案します:
– 配列を使用する 1 ライン内の要素の次元の流れ 2 ファイル内の.
– 配列内のkを見つけるための再帰的アルゴリズムの構築.

例:
TIMKIEM.INP
6 8
9 2 8 3 1 4
TIMKIEM.OUT
2
この記事は星を解読する

返信
ホーティタントゥ 言う:

6月 4, 2020 アット 1:57 午後

以下の関数で設定されたアルゴリズムの時間の複雑さを計算します:
私は(int型のn){
もし (n == 0) リターン 0;
そうでなければnを返す + 合計(-1);
}
このレッスンがいかに複雑であるかをお聞きします、先生?

返信