• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

5-b 시간복잡도

23.11.20 14:54 작성 23.11.20 15:04 수정 조회수 74

0

다른질문과 비슷한 질문인데 이해가 잘 안가서 좀 더 자세한 답을 부탁 드리고자 합니다.

#include <bits/stdc++.h>

using namespace std;

int n;

vector<pair<int,int>> v;

int a, b;

priority_queue<int, vector<int>, greater<>> pq;

int ret;

string s,f;

int main()

{

 

cin >> s>>f;

 

while (s.find(f) < s.size())

{

int n = s.find(f);

s.erase(n, f.size());

//cout << s<<"\n";

}

if (s.size())

cout << s << "\n";

else

cout << "FRULA" << "\n";

}

제 코두의 경우 시간복잡도가 O(N)이 아니라 O(n^2) 인 이유를 좀만 자세하게 설명해주시면 감사하겠습니다. 비슷한 질문 답변 내용이 이해가 잘 안되서 한 번 더 잘문드립니다.

 

저는 천만의 경우 1000만 + 999만 999 + ... 1 이라고 생각이 되서요 ㅠㅠ.

while 안에서의 시간복잡도 계산이라 더 이해가 안가는 것 같기도 합니다..

답변 1

답변을 작성해보세요.

0

안녕하세요 0508님 ㅎㅎ

저는 천만의 경우 1000만 + 999만 999 + ... 1 이라고 생각이 되서요 ㅠㅠ.

while 안에서의 시간복잡도 계산이라 더 이해가 안가는 것 같기도 합니다..

>> 이게 N^2이라고 보시면 됩니다.

이는 등차수열이라고 보시면 됩니다. 1000만이 초항, -1이 등차인 수열이죠. 그렇게 되면

등차수열의 합 공식에 의해서

1000만 * (1000만 - 1) / 2가 됩니다. 즉, 이는

N곱하기 N - 1 / 2가 되기 때문에 상수항을 제거하면 O(N^2)가 됩니다.

참고로 등차수열의 합은 교안 참고부탁드립니다.


또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.