이 코드 조각의 시간 복잡도는 얼마입니까?

void push(const Type& e){ 
     if (size() == CAP) { 
      CAP = CAP + 100; 
      Type * Snew = new Type[CAP]; 
      for (int i = 0; i < CAP - 100; i++){ 
       Snew[i] = S[i]; 
      } 
      delete[] S; 
      S = Snew; 
     } 
     TOP++; 
     S[TOP] = e; 
    }

이 알고리즘의 복잡도는 얼마이며 그 이유는 무엇입니까? 나는 그것을 잘못보고 있지 않기를 바라지 만, 하나의 for 루프의 존재로 인해 선형 시간 (O (n))의 복잡성을 갖고 있다고 생각하며, 루프 외부의 다른 모든 연산은 일정 시간 작동.이 코드 조각의 시간 복잡도는 얼마입니까?

출처

2015-02-01 user11892

코드에'n '이 없다는 것을 제외하면 올바른 것입니다. 시간 복잡도는'O (CAP)'입니다. –

루프 내부의 size()와 할당은 복잡 할 수 있으므로 자세한 정보없이 질문에 답할 수 없습니다. 또한 아마 상환 된 비용, 즉 함수를 n 번 호출하면 함수를 호출하는 평균 비용을 고려할 수 있습니다. 이렇게하면 누락 된 코드가 모두 O (1)라고 가정 할 때 CAP + 100 (평균 비용 O (n))과 CAP * 2 (평균 비용 O (1)) 사이의 차이가 나타납니다. –

그건 O (n)입니다. new의 구현에 따라, 그것은 상수 대신에 O (n) 일 수도 있지만 (mem 또는 뭔가 지우는 경우), 여전히 모든 것을 O (n)로 만듭니다.

출처

2015-02-01 06:45:12

복잡도는 O (n)입니다. 그러나 대부분의 스택 구현은 상각 된 상수 시간을 얻기 위해 고정 된 양만큼 증가시키지 않고 배열의 크기를 두 배로 늘립니다. 자세한 내용은 Constant Amortized Time을 참조하십시오.

출처

2015-02-01 10:35:17 markusk

이 코드 조각의 시간 복잡도는 얼마입니까?

답변

관련 문제