時間複雑度関数とbigo

時間の複雑さ

 
1.入力された個数がnである場合、時間複雑度関数T(n)間の関係はかなり複雑である可能性がある.
Ex) T(n) = n^2 + n + 1
 
しかし,nの値が大きいほどn^2+n+1におけるn+1の比重は小さくなる.
Ex)n=1000の場合,n^2(100万)+n(1000)+1となる.
n^2は99.9%を占めています
 
3.大文字記号は、時間複雑度関数の増加にあまり寄与しない項目を省略する.
Ex)T(n) = n^2 + n + 1
でn+1を省略し、n^2のみを残す
Oになります(n^2).
(第1、2、3条の内容は千人国、孔勇海、何尚浩の著者のC言語で書かれた3版の資料構造の修正を参考にした.)
 
ヴィクトオのグラフを見せてください
x軸は入力データのサイズnである.
y軸はアルゴリズムの実行に必要な大きなO()を表す.

画像ソース:https://velog.io/@zxcvbnm 5288/nov.10-2020-Big-O-Natation big-o記号
 
速度.
O(1)が一番速い.
O(1) > O(logn) > O(n) > O(n^2) > O(n^3) > O(n^n)
順番に速く見えます.
 
5.ソースコードからヴィオを知ることができれば
ソースコードの時間的複雑さを決定します.
これにより、より高速なソースコードを記述できる視野が得られます.
 
6.ソースコードを見せてあげます.
時間複雑度関数T(n)とVIGOを同時に把握する.
解説と答えはコメントに!

#include<stdio.h>
#include<windows.h>

int main()
{
int i = 0;
int n = 0;
printf("데이터 n개를 입력하세요\n");
scanf("%d", &n);

printf("n이 몇개든 곧바로 실행되면 O(1)\n");

for (i = 0; i < n; i++)
{
	Sleep(1000); //1초동안 멈춤
}

printf("데이터 n을 입력할 때 n번의 루프 후 실행 완료되면 O(n)\n");

for (i = 0; i < n; i++)
{
	for (int j = 0; j < n; j++)
	{
		Sleep(1000); //1초동안 멈충
	}
}
printf("데이터 n을 입력할 때 n^2번의 루프 후 실행 완료되면 O(n^2)\n");

//시간복잡도 함수로 T(n) = n^2 + n + 1;
//빅오 O(n^2)
//n이 1000이면 n^2(1000000)초 + n(1000) 초 + 0초가 걸린다.
//n이 클 수록 n+1의 비중은 미미하므로, 시간 복잡도 향상에 기여하지 못하는 항은 생략하는 것
}

 
注意:https://velog.io/@zxcvbnm 5288/nov.10-2020-Big-O-Natation big-o記号
参考書:「千人国」、「公共海」、「河床湖」、「C言語易解資料構造改訂三版」、「生能」出版