시간복잡도를 계산해 보세요.

일반적인 행렬곱셈으로 풀었을 때를 말하시는 건가요?

네.

시간복잡도 구하는 것에서 어떻게 힌트를 얻죠..? 당연히 O(n^3)인 건 저도 알고 있는데요..대답이 너무..무성의하네요.

시간복잡도와 실제 입력의 범위를 비교해 보면 시간 안에 돌아가는 지 예측할 수 있으니까요. 최대값을 넣었을 때 10^8 이하면 충분히 통과됩니다.

참고로 N은 행렬의 개수니까 O(N^3)은 아닙니다.

직접 시간복잡도를 계산해보고 실제 연산량을 측정해보라는 의미에서 저렇게 쓰신 겁니다. 무성의하다니요... 답변자에게 항상 성의를 바라시는건가요;

100*(50^3)이면 12.5만 * 100만 = 1250만인데요..

애초에 행렬 갯수 N이랑 최대 가로, 세로 사이즈 s가 다릅니다. 그러니 O(Ns^3)으로 계산하셔야 합니다.

반복문 4개가 중첩된다고 해도

for(int i=0;i<100;i++)

  for(int j=0;j<100;j++)

    for(int k=0;k<100;k++)

      for(int w=0;w<100;w++)

이거랑

for(int i=0;i<100;i++)

   for(int j=0;j<100;j++)

      for(int k=0;k<2;k++)

        for(int w=0;w<3;w++)

이거랑 수행 시간 자체가 다른데요. gk님 말대로라면 둘 다 4중 중첩문이니까 O(n^4) 아닌가요..??

뭔가 헷갈리시는 거 같네요. 

반복문 중첩이 4개 = O(n^4)꼴이다.. 이런 생각을 하신 건데.. 말이죠..

이런 식으로 이해하신다면 에라스토스테네스의 체 수행시간이 n^2 아닌가요? 그렇게 이해하실 듯 싶네요.

for문 2개 있다고. 

실제로는 nloglogn인데.

생초보라서 뭔말인지 몰랐습니다. 죄송합니다.