이렇게 sleve가 500만인 경우.. 배열의 크기 자체가 엄청나게 크기 때문에, 오래 걸릴 수 있어요.

또 다른 이유는 Sieve[x]에 x의 소인수들을 모두 저장하는 거 같은데요. 공간 복잡도가 어떻게 될까요? 

에라스토스 테네스의 체 복잡도만큼 된다. 정도로 요약하면 될 겁니다. 여기서 아껴지는 공간은..

루트(500만) 보다는 크면서, 소수인 것 만큼은 절약될 수 있겠네요.

대략적으로 공간 복잡도가 O(nloglogn)쯤 될 건데.. 500만 x log28 = 2천만 ~ 3천만입니다.

제가 3시에 수업이라 자세히는 설명 못 드리고, 수업 시간에 자세히 답변 드릴게요.

모르는 내용을 또 새로 배워가는 느낌이네요.

코드를 짜면서 공간복잡도가 좀 커지긴 하겠지만 그게 시간엔 영향을 안주겠지 생각했는데, 짧은 식견이였나 보네요.

어쨌든 자세히 써주시면 감사히 읽도록 하겠습니다. 

늦었네요. 일단 답변 드리겠습니다..

1.

vector push_back에 대해서

(1)

동적 배열이라는 말을 들으셨을지도, 안 들으셨을 지도 모르겠습니다만.. 쉽게 이야기 해 봅시다.

보통 int arr[30000]; 이런 식으로 할당되는 것을 정적 배열이라 합니다. 고정 배열이라고 하나요? 정확한 용어는 잘 모르겠다마는.

저 것의 의미는 int형 데이터가 3만개가 있는 array를 선언한다는 겁니다. 문제는. 저건, 3만개짜린데 6만개, 9만개 짜리로 확장할 수 없습니다. 맞나요?

동적 배열은 그게 아닙니다. 크기가 정해지지 않았다. 변할 수 있다는 겁니다.

예를 들어 처음에 20개짜리 int형 배열을 선언했다. 요소가 추가됨에 따라서 40개, 80개, 160개 등으로 변하게 할 수 있을 겁니다.

이것이 쉽게 말해서 동적 배열 (Dynamic array) 라고 합니다. 그냥 동적 할당의 동적과 동적 배열의 동적과 똑같은 개념이라고 생각하시면 이해가 굉장히 편하실 거에요.

문제는 얘가 어떻게 동작을 하느냐인데.

push_back이 호출이 될 때 마다, 공간을 1씩 늘려주면 어떨까요? 현재 vector의 size를 n이라 한다면

n+1짜리 공간을 만들어야 할 거고요. n짜리 공간에 있는 데이터를 n+1짜리 공간으로 copy 해야 할 거고. n짜리를 delete 해야 할 겁니다.

O(3n+1) = O(n)인가요? 이걸 push_back이 호출될 때마다 하면 곤란하겠죠..?

그래서, 공간이 부족할 때 하나씩 확장을 하는 게 아니라 x배율로 새로 확장을 하는데 c++의 vector는 x = 2입니다.

(2)

그러면 이 때, 복잡도를 구해 봅시다. 벡터의 초기 size가 1이라고 했을 때.

1

2

4

8

16

32

64

...

2^n

크기가 2^n인 벡터가 있다고 해 봅시다. 초기 size가 1이다. 그러면

크기가 1인 상태에서 추가될 때 => 3*1+1

크기가 2^2-1인 상태에서 추가될 때 => 3*(2^2-1)+1

...

크기가 2^n-1인 상태에서 추가될 때 => 3*(2^n-1)+1

이런 식으로 되겠네요.

Total 연산 횟수를 op라고 한다면 op<3*(2^1+...+2^n) + n입니다.

등비 수열의 합 공식에 의해서, 이는 3*2*(1+...+2^(n-1)) + n이 되고

이것은 다시 6*(2^n-1) + n이 됩니다. n<<2^n이므로, 시간 복잡도는 2^n에 의해서 결정되겠네요.

N = 2^n이라고 했기 때문에, N개만큼 추가될 때 복잡도가 O(N)이다. 정도로 말을 할 수 있습니다.

이 배율을 grow_rate라고 합니다.

2.

그러면 일반적인 배열하고 같느냐. 물론 같습니다. 하지만, growth rate가 2라는 걸 역으로 생각해 봅시다.

초기 size가 1이고, capacity가 1이라고 해 봅시다. grow rate가 2라고 하고요. 그러면. 대충

(size,capacity)로 표시할게요.

(1,1) (2,2) (3,4) (4,4) (5,8) (6,8) (7,8) (8,8) (9,16) ... (2^n,2^n) (2^n+1,2^(n+1)) ...

1<=(capacity/size)<2라는 것을 알 수 있어요.

정 궁금하시다면. 아래 소스 코드를 실행해 보세요.

하튼. 그렇다는 이야기는, 할당된 실 크기가, 원래 벡터 원소 갯수 대비 최대 2배 가량까지 늘어날 수 있다는 겁니다.

배열의 크기가 500만인 상황에서는, 각 요소 하나 당, 추가되는 원소가 늘어날수록, 메모리 공간도 엄청나게 커지는 구조이고.

심지어 500만이면, int형으로 저장을 한다고 해도 20메가입니다. 그런데 

제가 위에서 분석해 드렸던 공간 복잡도를 그대로 적용하면 대략 O(nloglogn)입니다. n이 무지하게 크니까 대략 3-4천만 되겠네요.

4천만개.. 거기에 벡터는 최악의 경우에는?? 2배?

공간이 어마무시하게 늘어나는 건 자명해 보입니다. 그게 시간하고 연결이 됩니다.

160메가라면 무지막지하게 크기 때문에, cache.. 잘 써먹질 못하겠죠. 심지어 벡터의 특성상.

요소 하나 하나가 동적으로 할당이 되는데.. 물론, vector 자체는 연속적이겠다마는. 그러면 상대적으로 배열에 저장할 때 보단 띄엄띄엄 하지 않을까요?

Sieve[2] - 2

Sieve[3] - 3

...

Sleve[12] - 2 3

마치, 

Sieve[2] = (int *)malloc(sizeof(int)*...);

Sieve[3] = (int *)malloc(sizeof(int)*...);

이런 꼴인데. 동적 할당은, 어디에 할당될 지 며느리도 모르죠.. 결국 띄엄띄엄 저장될 거고. 

이건 Locality가 상대적으로 떨어지는 결과를 불러올 거에요.