말씀하시고자 하는 바가 무엇인가요.
그래서 결론적으로 O(n^4) 가 되야된다? 는 아니겠죠 물론.
O(n^3) 이라는 걸 원론적인 의미 빼고 그냥 코드 레벨에서 보면
n 번의 루프가 3개 중첩이 된다는 의미인데, 말씀하신 대로
작업이 끝나고 다시 n번 루프 하나 도는 것은 중첩이 아니죠.
이건 물론 아실테고, 그럼 결과적으로 그래봐야 f(n) = n^3 + n 인데
당연히 원래 빅오표기법대로 최대 차수항만 의미있으니 결국 전체적으로 O(n^3) 입니다.
n^3 루프가 하나 있는 한 뒤에서 n^2 루프를 1000번 하던 10000번 하던 전체는 O(n^3) 입니다.
으음?
연산 하나하나마다 판단하여
최소값이라면 갱신을 그러한 과정 자체가 하는게 최적의 path를 탐색하는게 아닌가요?
따로 O(n)이 필요하다는 얘기를 들어보진 못했습니다
벨만포드의 결과 테이블
벨만 포드의 결과 테이블이
각 vertex 마다의 코스트와 vertex를 가르키는 vertex( prev vertex)로 구성되 있는걸로 알고있습니다
vertex 1 2 3 4 5
cost a b c d e
prev_vertex -1 1 2 3 4
그렇다면 5를 가귀 위한 cost는 단 번에 알수 있지만
가는 경로 같은경우는 다익스트라처럼 따로 저장하면서 진행하는게 아니고
역 추적하면서 계산해야되는데 이 과정이 최대 N까지 가는 것 같은데
이게 왜 고려되지 않는가를 물어보는 질문 이었는데
벨만포드 정의 자체는 코스트까지만 계산하는 것 같습니다..
f(n)∈O(n^3)이고 g(n)∈O(n)이면 f(n
f(n)∈O(n^3)이고 g(n)∈O(n)이면 f(n)+g(n)∈O(n^3)
증명은 연습문제로 남깁니다.
.
말씀하시고자 하는 바가 무엇인가요.
그래서 결론적으로 O(n^4) 가 되야된다? 는 아니겠죠 물론.
O(n^3) 이라는 걸 원론적인 의미 빼고 그냥 코드 레벨에서 보면
n 번의 루프가 3개 중첩이 된다는 의미인데, 말씀하신 대로
작업이 끝나고 다시 n번 루프 하나 도는 것은 중첩이 아니죠.
이건 물론 아실테고, 그럼 결과적으로 그래봐야 f(n) = n^3 + n 인데
당연히 원래 빅오표기법대로 최대 차수항만 의미있으니 결국 전체적으로 O(n^3) 입니다.
n^3 루프가 하나 있는 한 뒤에서 n^2 루프를 1000번 하던 10000번 하던 전체는 O(n^3) 입니다.
댓글 달기