Гипотеза о вычислительной сложности алгоритмов.

Пусть есть задача (проблема) размера N. Пусть также существует (известен) алгоритм (метод, способ) решить эту задачу за время O(N*N), и существует способ проверки корректности решения за время O(N).
Тогда существует алгоритм решения этой задачи за время O(N*logN).

Пример 1. Сортировка массивов. Существует алгоритм сортировки за время O(N*N). Корректность работы алгоритма сортировки можно проверить за время O(N). Следовательно, существует алгоритм сортировки за время O(N*logN).

Пример 2. Перемножение длинных (больших) целых чисел (миллионы цифр). Их можно перемножить за время O(N*N). Результат можно проверить за время O(N) с некоторой заранее заданной достоверностью, например, 0,999999... . Следовательно, существует алгоритм перемножения чисел за время O(N*logN).

Есть ли контрпримеры? Ищу их.

Какие перспективы у электрических самолётов на солнечных батареях?

Для оценки перспектив сравним самолёт на фотовольтаике с электрическим самолётом на аккумуляторных батареях.

Аккумуляторы:
Запас энергии – порядка 250 Вт*ч на кг.
Удельная мощность зависит от скорости разряда аккумуляторов, которая в общем случае может быть любой. При токе разряда 1C аккумулятор разрядится за 1 час, это же означает, что самолёт будет летать 60 минут. При токе 10C аккумулятор разрядится за 6 минут, но тогда и самолёт будет летать 6 минут. Летая со скоростью звука, за 6 минут он пролетит 108 км, такое расстояние вряд ли интересно для авиапассажиров. Значит, можно считать, что скорость разряда будет не выше 4C, соответственно, удельная мощность – 1000 Вт на кг (250 Вт*ч за 15 минут) или меньше.

Фотовольтаика:
Запас энергии – неограничен, пока светит Солнце.
Удельная мощность – сообщают о 44 Вт на грамм. Скорее всего, фотовольтаику придётся куда-то крепить – квадратный метр сотового поликарбоната 4 мм весит 0,5 кг. Получается, 250 Вт на 0,5 кг или 500 Вт/кг.

Вывод:
По удельной мощности (Вт/кг) фотовольтаика сравнима с аккумуляторами, а по удельной энергии (Дж/кг) превосходит их. Перспективы электросамолётов на солнечных батареях выглядят не хуже таковых для аккумуляторных самолётов. Возможно, солнечные самолёты займут свою нишу, например, для дальних перелётов.