Посчитай вычислительную сложность программы с объяснением #include <ctime> #include <iostream> int main() { const int max = 20000; bool arrayA[max + 1]{false}; bool arrayB[max + 1]{false}; int number = 0; // std::cout << "Input A." << std::endl; while

24 октября 2025
Программирование

Условие:

Посчитай вычислительную сложность программы с объяснением
#include <ctime>
#include <iostream>

int main()
{
const int max = 20000;
bool arrayA[max + 1]{false};
bool arrayB[max + 1]{false};

int number = 0;

// std::cout << "Input A." << std::endl;

while (true) {
std::cin >> number;

if (number == 0)
break;
if (number >= 1 && number <= max) {
arrayA[number] = true;
}
}

// std::cout << "Input B." << std::endl;

while (true) {
std::cin >> number;

if (number == 0)
break;
if (number >= 1 && number <= max) {
arrayB[number] = true;
}
}

// std::cout << "Result:" << std::endl;
clock_t startTime = clock();

bool found = false;
for (int i = 1; i <= max; ++i) {
if (arrayA[i] != arrayB[i]) {
std::cout << i << " ";
found = true;
}
}

if (!found) {
std::cout << 0 << std::endl;
} else {
std::cout << std::endl;
}

std::cout << (startTime - clock()) / 1000.0 << std::endl;

return 0;
}

Решение:

Разберём программу по шагам и оценим её вычислительную сложность. 1. Объявляются два булевых массива arrayA и arrayB размера max+1, где max = 20000. Создание массивов занимает O(max). 2. Первый цикл ввода (while) считывает числа для набора A. Каждый ввод проверяется, равно ли число нулю (условие завершения) и находится ли оно в диапазоне [1; max]. В худшем случае, если пользователь введёт все во...