Python 알고리즘 표현 개념 활용 능력에 대한 예제 튜토리얼

이 글은 주로 Python 알고리즘 표현 개념 이해 튜토리얼을 자세히 소개하며, 관심 있는 친구들이 참고할 수 있습니다.

이 글은 모든 사람을 위해 Python 알고리즘 표현 개념을 설명합니다. 구체적인 내용은 다음과 같습니다.

상수차 O(1)

상수는 고정수라고도 하며, 수치가 변하지 않는 상수를 말합니다. 그 반대는 Variable

다음 알고리즘의 시간복잡도는 왜 O(3)이 아니고 O(1)인가?

int sum = 0,n = 100; /*执行一次*/ 
sum = （1+n）*n/2; /*执行一次*/ 
printf（"%d", sum）; /*行次*/

이 알고리즘의 실행 횟수 함수는 f(n)=3입니다. Big O 차수를 도출하는 방법에 따르면 첫 번째 단계는 상수 항 3을 1로 변경하는 것입니다. 최고차 항을 유지할 때 최고차 항이 전혀 없다는 것을 알았으므로 이 알고리즘의 시간 복잡도는 O(1)입니다.

게다가 이 알고리즘에 10개의 문 sum=(1+n)*n/2이 있다고 가정해 보겠습니다.

int sum = 0, n = 100; /*执行1次*/ 
sum = （1+n）*n/2; /*执行第1次*/ 
sum = （1+n）*n/2; /*执行第2次*/ 
sum = （1+n）*n/2; /*执行第3次*/ 
sum = （1+n）*n/2; /*执行第4次*/ 
sum = （1+n）*n/2; /*执行第5次*/ 
sum = （1+n）*n/2; /*执行第6次*/ 
sum = （1+n）*n/2; /*执行第7次*/ 
sum = （1+n）*n/2; /*执行第8次*/ 
sum = （1+n）*n/2; /*执行第9次*/ 
sum = （1+n）*n/2; /*执行第10次*/ 
printf（"%d",sum）; /*执行1次*/

사실 n이 무엇이든 상관없습니다. , 위의 두 코드 조각은 3번 실행과 12번 실행의 차이입니다. 문제의 크기(n의 크기)에 관계없이 일정한 실행 시간을 갖는 이 알고리즘을 O(1)의 시간 복잡도라고 하며, 상수 차수라고도 합니다.

참고: 상수가 무엇이든 상관없이 O(3), O(12) 등과 같은 다른 숫자가 아닌 O(1)로 기록합니다. 이는 자주 저지르는 실수입니다. 초보자.

Big O 방식의 도출

1. 실행시간의 모든 덧셈 상수를 상수 1로 대체

2 수정된 실행 횟수 함수에서는 최상위 항

3만 유지됩니다. 최상위 항이 존재하고 1이 아닌 경우 해당 상수

를 제거합니다. 로그 차수 O(log2n)　

로그

x의 거듭제곱이 같다면 N(a>0, a는 1이 아님)에 대해 숫자 x는 a를 밑으로 하는 N의 로그(로그)라고 하며 x=logaN으로 기록됩니다. 그 중 a를 로그의 밑수, N을 실수라 부른다.
5^2 = 25, 2= log5 25로 기록됨
대수는 연산이고 지수는 역수 연산입니다. 예를 들어

① 3^2=9 <==> 2=log<3>9

② 4^(3/2)=8 <==> 3 /2=log<4>8;

3 10^n=35 <==>n=lg35. 사용하기 쉽도록 밑이 10인 상용 로그를 lgN

로그 순서

int count = 1; 
while (count < n) 
{  
count = count * 2; /* 时间复杂度为O(1)的程序步骤序列 */ 
}

로 기록합니다. 각 개수부터 2를 곱한 후, n에 한 지점 더 가깝습니다.

즉, 2를 곱한 값이 n보다 큰 경우 루프가 종료됩니다.

2^x=n에서 x=log2n을 얻습니다. 따라서 이 루프의 시간 복잡도는 O(logn)입니다.

선형 순서 O(n)　　

문제 크기에 비례하여 실행 시간이 증가합니다

data = [ 8,3,67,77,78,22,6,3,88,21,2]
find_num = 22
for i in data:
  if i == 22:
    print("find",find_num,i )

선형 로그 순서 O(nlog2n )

제곱차 O(n^2)

for i in range(100):
 
  for k in range(100):
    print(i,k)

삼차차 O(n^3)
k번제곱 차수 O(n^k),
지수 차수 O(2^n).

문제 크기 n이 계속 증가함에 따라 위의 시간 복잡도는 계속 증가하고 알고리즘의 실행 효율성은 낮아지게 됩니다. ​

위 내용은 Python 알고리즘 표현 개념 활용 능력에 대한 예제 튜토리얼의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!