effort0819   2년 전

공간복잡도 구할때 코드가 아래와 같다면

배열 : N*3

x,y,N : 3

for문안의 a,b,c : N*3

이렇게해서 6*N + 3 을해야하나요..?

공간복잡도 구하는 방법을 잘 모르겠네요..

struct test{

      int a;

      int b;

      int c;

}

int main(){

      int x,y,N;

      // N입력

      test array[N];


      for(int i=0; i<N; i++){

            int a, b, c;

            // a,b,c 입력

            // test[i] a,b,c를 가진 test instance 추가

      }

}

djm03178   2년 전

for문 안의 a, b, c는 루프가 한 번 돌 때마다 생성되고 그 루프가 끝날 때 소멸되기 때문에 한 번만 생성되는 걸로 보아도 됩니다.

그리고 복잡도의 개념상 상수곱과 상수항은 전혀 고려할 필요가 없습니다. 최고차항의 차수가 어떻게 되는지만 보면 됩니다. 여기서 최고차항은 4N이므로 4배는 무시하고 O(N)이라고 쓰면 됩니다.

effort0819   2년 전

@djm03178

왜 4N인지 이해가안가는군요 ㅠ ㅠ..

배열 인자가 3개의 변수를 가지므로 3N아닐까요?

djm03178   2년 전

앗 잘못 생각했네요. 그런데 말씀드렸다시피 3N이나 4N이나 10000000N이나 복잡도상으로는 전혀 차이가 없습니다.

상수배를 따지자면 구조체 내의 변수 하나하나가 4바이트씩 먹는다고 생각하면 12N도 될 수 있고, 비트 수로 32비트씩이라고 생각하면 96N일 수도 있고, 별로 의미가 없습니다.

effort0819   2년 전

@djm03178

결론은 3N+8 이나오든 4N+12가 나오든 Big-O 표기법으로는 O(N)이 된다는 거군요! 감사합니다 ㅎㅎㅎ

댓글을 작성하려면 로그인해야 합니다.