Задать вопрос
niten_d0raku

niten_d0raku

Лайки

  • Какая сложность у std::sort?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    Это ассимптотическая сложность O(n log n). В ассимптотической сложности константа не имеет значения. И 2n, и 1000n - все одно O(n). При изменении основания логарифма у вас появится лишь константный множитель, который O() игнорирует, ведь log_а (n) = log_b(n) / log_b(a). Поэтому можно использовать вообще любой логарифм.

    В компьютерной науке обычно используют логарифм по основанию 2. Потому что в алгоритмах вылезает именно деление на 2, а не на 10 и тем более не на e.
    Ответ написан

  • Какая сложность у std::sort?

    @Mercury13
    Программист на «си с крестами» и не только
    Символ Ландау g(x) = O(f(x)) при x→y означает: g(x)⩽kf(x) при x, достаточно близких к y. В данном случае y=∞.
    То есть с точностью до константы. А как Wataru сказал, основание логарифма — это умножить на константу.

    А я попытаюсь сказать, почему удобны символы Ландау.
    1. Математическим исследованием сложно выяснить, сколько операций займёт одна итерация цикла — две или тысячу. Этим пусть занимаются микрооптимизации.
    2. Зато в любую программу загонят столько данных, что она сломается. И как правило — если не доказано обратное — асимптотическая сложность быстро пересилит эту самую константу, и программа большей сложности сломается первой.
    3. Ну вот прога сломалась, и мы занялись микрооптимизациями и заменили процессор, и получилось, скажем, вдвое — насколько более крупные задачи мы теперь можем решать? Если O(N), то вдвое более крупные. Если O(N log N), то несколько меньшие, чем вдвое. А если O(N²), то в 1,4 раза.
    Ответ написан

  • Как вернуть двумерный массив?

    wataru
    @wataru Куратор тега C++
    Разработчик на С++, экс-олимпиадник.
    int masInt[3][5] - вот такие массивы c фиксированными размерами на самом деле хранятся одним куском и индексацию компилятор вычисляет сам. Это не int**, а int[][5]. Только этот тип нельзя вернуть из функции.

    Что бы вернуть именно указатель на указатель, вам надо его так и завести и не забыть выделить по строкам:
    int** masInt = new int* [3];
for (int i = 0; i < 3; ++i) {
  masInt[i] = new int[5];
}


    Не забудьте только потом удалить все это добро через delete[]:
    for (int i = 0; i < 3; ++i) {
  delete[] array[i];
}
delete[] array;


    Но вообще, лучше не парить себе мозги и возвращать std::vector<std::array<int,5>>.
    Ответ написан
    1 комментарий
    1 комментарий

  • Как подключить tdlib к проекту c++ в msvs?

    @dima20155
    you don't choose c++. It chooses you
    Вам нужно указать библиотеку в настройках линковщика
    https://learn.microsoft.com/ru-ru/cpp/build/adding...
    Ответ написан
    12 комментариев
    12 комментариев