안녕하세요 빅오 표기법 혹시 도움주실분 계실까요..

Question

안녕하세요. 이번에 막 신입생으로 들어간 사람입니다 ㅠㅠ 교수님이 빅오 표기법,시간 순서도 과제를 주셨는데 아무리보고 또 봐도 도무지 모르겠습니다...혹시 도움 주실분이 계실까요...?for ( i ← 1; i <&#61;n ; i ← i &#43;1) do { for (r ← 0; r < 10; r ← r&#43;1) do { A ← A &#43; B ; } } 이 부분입니다.. 도움주시는 모든분들 감사합니다.

guyv · Answer

chatgpt 에게라도 물어보는 노력이라도 해보십시오~

개린양 · Answer

이 코드의 시간 복잡도는 O(n) * O(10) 이므로 O(n)입니다.바깥쪽 for 루프는 n번 반복하고, 안쪽 for 루프는 상수 시간 복잡도 O(10) 내에서 실행됩니다. 따라서 전체적인 시간 복잡도는 O(n) * O(10) = O(n)입니다. 라고 하네요 우리 챗교수님은~

songline · Answer

빅오 표기법은 조건, 반복문이 돌 때 발생할 수 있는 최악의 시간 복잡도를 의미하는 것입니다.일반적으로 컴퓨터에서 수행하는 반복 횟수는 몇십, 몇백번 정도가 아니기 때문에 30n 보다 n^2가 훨씬 오랜 시간이 소요됩니다. 그래서 2n^2 + 47n + 894 이런것도 다 자르고 최고차항의 지수만 보아 O(n^2) 이런식으로 표기합니다.반복문을 수행하고 다른 반복문을 수행하면 시간 복잡도는 더하면 됩니다. O(n) + O(n) = O(n)반복문 안에서 다른 반복문이 돈다면 시간 복잡도는 곱하면 됩니다. O(n) * O(n) = O(n^2)이진 탐색이 적용된 코드는 효율이 지수적으로 개선됩니다. O(n) => O(log_n) (여기서 log는 밑이 2인 log)

안녕하세요 빅오 표기법 혹시 도움주실분 계실까요..

3개의 답변

기타 목록