버블 정렬 알고리즘 찾기 시간 복잡도

Question

내가 일종의

n=length[A] 
for j <- n-1 to 1 
for i <- 0 to j-1 
if A[i]>a[i+1] 
temp=A[i] 
A[i]=A[i+1] 
A[i+1]=temp 

return A 

중 하나가 우리가 배열의 길이를 할당하는 라인 1에 감사

Answer 1

• 도움을 주시기 바랍니다 거품의 시간 복잡도를 찾기 위해 노력하고있다 n so constant time
• 2 번째 줄에는 j = 1이 될 때까지 j를 1 씩 감산하고 총 n-2 회 반복하는 for 루프가있다.
• 첫 번째 for 루프 내부에는 i = j-1이 될 때까지 i를 1 씩 증가시키고 j-1 회 반복 할 두 번째 for 루프가 있습니다. inner for 루프의 각 반복에서 4,5,6,7 행이 모두 할당되고 배열 액세스가되며 총 비용은 일정 시간입니다.
• 우리는 두 가지 루프에 대해 다음과 같이 생각할 수 있습니다. for 루프의 모든 반복에 대해 inner for 루프는 j-1 번 반복합니다.
• 따라서 외부 for 루프의 첫 번째 반복에서 우리는 j = n-1이됩니다. 즉 inner for 루프는 (n-1) -1 = (n-2) 회 반복 할 것입니다. 그런 다음 outer for 루프의 두 번째 반복에서 j = n-2이므로 내부 for 루프는 (n-2) -1 = (n-3) 번 반복 할 것입니다. 그리고 우리는 j = 1이 될 때까지 이것을 수행합니다.
• 그러면 내부 루프가 반복 할 총 횟수 인 (n-2) + (n-3) + ... + 2 + 1 방정식을 갖습니다. 전체 알고리즘이 실행 된 후 1 + 2 + ... + n-1 + n = n (n-1)/2이므로 우리의 표현은 다음과 같이 간단해질 수 있습니다. n (n-1)/2 - (n-1) -n = n (n-1)/2 -2n + 1 = O (n^2)이다.
• 우리의 inner for 루프는 O (n^2) 번을 반복 할 것이고 각 반복마다 상수 작업을 수행하므로 런타임은 O (cn^2)가 될 것입니다. 여기서 c는 라인에 의해 수행되는 지속적인 작업의 양입니다 4,5,6,7. O (cn^2)를 O (1) 인 1 행과 결합하면 O (cn^2) + O (1)은 O (n^2)뿐입니다.
• 따라서 BubbleSort의 런타임은 O (n^2)입니다.

여전히 혼란스러워하는 경우 어쩌면이 도움이 될 것입니다 https://www.youtube.com/watch?v=Jdtq5uKz-w4