글 읽기 - 왜 시간복잡도가 걸릴까요 c++

mychan0926 1년 전 0

a+a번 돌기때문에 시간복잡도가 그리 크지 않을거같은데,, 왤캐 걸릴까요

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


using namespace std;

void BS(vector <int> &k,int a,int e,int f)
{   
    while (1)
    {  
        if (((f-e)) % 2 == 0)
        {
            if (k[((f-e)) / 2 + e] > a)
            {

                BS(k, a, e, ((f-e)) / 2 +e);
                break;
            }
            else if (k[((f-e)) / 2 + e] < a)
            {
                BS(k, a, ((f-e)) / 2+e,f);
                break;

            }
            else if(k[((f-e)) / 2 + e] == a)
            {
               
                
                cout<< "1 ";
                break;

            }
        }
        else
        {

            if (((f-e))==1 && k[0]!=a)
            {
                cout << "0 ";
                break;
            }
            else if (k[(((f-e))-1) / 2 + e] > a)
            {
                BS(k, a, e, (((f-e)) - 1) / 2+e);
                break;
            }
            else if (k[(((f-e)) - 1) / 2 + e] < a)
            {
                BS(k, a, (((f-e)) - 1) / 2 +e, f);
                break;
               
            }
            else if (k[(((f-e)) - 1) / 2 + e] == a)
            {


                cout << "1 ";
                break;


            }
        }
    }
}


int main()
{
    int a,b,c,d,e,N,M;
    vector <int> s;
    cin >> a;


    for (int i = 0; i < a; i++)
    {
        int j = 0;
        cin >> j;
        s.push_back(j);


    } 
    sort(s.begin(),s.begin()+a);
    cin >> b; 
    for (int i = 0; i < b; i++)
    {
        int j = 0;
        cin >> j;

        BS(s, j,0,a);

    }

}

dbgmlwns 1년 전 0

BS의 시간 복잡도가 1인가요?

그리고 sort의 시간 복잡도가 O(n log n)으로 알고있습니당

mychan0926 1년 전 0

그럼 sort트를 사용하지않고 이붘탐색을 할수가 있나요?

dbgmlwns 1년 전 0

아뇨 sort는 상관 없는데 이분탐색 방법을 재귀 말고 for문으로 해보세요

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

문제

문제

출처

ICPC

왜 시간복잡도가 걸릴까요 c++

mychan0926 1년 전 0

dbgmlwns 1년 전 0

mychan0926 1년 전 0

dbgmlwns 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말