Как решить экспоненциальные ступенчатые циклы с помощью суммирования (i = 2i)

В этом видео мы разберем, как анализировать цикл, в котором переменная удваивается каждый раз (i = 2*i). Вместо того чтобы гадать о временной сложности, мы перепишем цикл, используя суммирование, и решим его шаг за шагом. Вы узнаете: 1. Как на самом деле работают циклы с экспоненциальным шагом 2. Почему цикл проходит через степени двойки 3. Как выразить цикл в виде суммирования 4. Сколько раз на самом деле выполняется цикл 5. Почему окончательный ответ имеет логарифмическое время (Θ(log n)) Это понятное, доступное для начинающих объяснение, идеально подходящее для всех, кто изучает алгоритмы, нотацию Big-O или готовится к собеседованиям по программированию. ★Подпишитесь, пожалуйста! https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ ★Простой учебник по анализу алгоритмов: https://www.udemy.com/algorithm-analysis/ ★Рекуррентные соотношения простым языком: https://www.udemy.com/recurrence-relation-made-easy/learn/v4/overview ►Видео по обходу дерева: (1) В порядке предварительного обхода: https://www.youtube.com/watch?v=9-JqWNwhEmQ (2) В порядке последующего обхода: https://www.youtube.com/watch?v=vFVkXpfJz94 (3) В порядке инкорпорации: https://www.youtube.com/watch?v=BFw0S8EL0Es (4) Пример обхода дерева: https://www.youtube.com/watch?v=sC2Am2nKkn4&t=16s ►Видео по дискретной математической индукции: (1) Индукционное суммирование: https://www.youtube.com/watch?v=O-8Jn8bkh30 (2) Математическая индукция делимости: https://www.youtube.com/watch?v=218LXrxglmU (3) Индукционное рекуррентное соотношение 1: https://www.youtube.com/watch?v=t_3ACuzEe_8 (4) Индукционное рекуррентное соотношение 2: https://www.youtube.com/watch?v=XWykCejG1Rk ►Видео по логической эквивалентности: (0) Логическая эквивалентность: https://www.youtube.com/watch?v=Wyd-PLf2mc0 (1) Тавтология: https://www.youtube.com/watch?v=N8yhE1GaaQc (2) Тавтология: https://www.youtube.com/watch?v=okZcT... (3) Противоречие: https://www.youtube.com/watch?v=YXSYB... ►Видео по асимптотике Big-O: (1) Решение Big O: https://www.youtube.com/watch?v=JVuHSouGKhk (2) Решение Theta: https://www.youtube.com/watch?v=Vzqaz4MDGvc (3) Решение Big Omega: https://www.youtube.com/watch?v=P2qHss2-aSQ (4) Объяснение обозначения Big O: https://www.youtube.com/watch?v=V4e34F3a-Eg ►Видео по суммированию: Решение в замкнутой форме: суммирование: https://www.youtube.com/watch?v=7qaGjr-FIu0 Анализ алгоритма: суммирование: https://www.youtube.com/watch?v=ACnD4e9Dd2Y Суммирование / Сигма Обозначения: https://www.youtube.com/watch?v=TY7tgPe2hQY Решение в замкнутой форме для суммирования: https://www.youtube.com/watch?v=HmRxPlV_nWo Вычисление суммы: https://www.youtube.com/watch?v=NN5NVKEhjMQ Временная сложность кода с использованием сумм: https://www.youtube.com/watch?v=4XkHbNi1ZL4 ►Видео о рекуррентных соотношениях: Доказательство рекуррентного соотношения методом индукции: https://www.youtube.com/watch?v=t_3ACuzEe_8 Время выполнения рекуррентного соотношения методом индукции: https://www.youtube.com/watch?v=XWykCejG1Rk Дерево рекуррентных соотношений: https://www.youtube.com/watch?v=vQt6ryhkYI0 ►Видео о пределе О, Омега, Тета: (1) Решение задачи об пределе Омега методом Пределы: https://www.youtube.com/watch?v=TPhV3xgEmHc (2) Решение задачи О больших пределов: https://www.youtube.com/watch?v=QhpfLwe-ERM (3) Доказательство задачи О малых пределов: https://www.youtube.com/watch?v=CjAiht0yt1s (4) Решение задачи Тета больших пределов: https://www.youtube.com/watch?v=lYykfmeKuA0 ♥ Посетите мой сайт: https://everythingcomputerscience.com/ ♥ Поддержите этот канал на Patreon: https://www.patreon.com/randerson112358 ♥ Полезные книги: ►Анализ алгоритмов Книги: https://www.amazon.com/gp/product/0262033844/ref=as_li_tl?ie=UTF8&tag=randerson112358-20&camp=1789&creative=9325&linkCode=as2&creativeASIN=0262033844&linkId=e0756ab4063fe56fe882b41f61612794 ►Рабочие тетради по дискретной математике: (1) Практические задачи по дискретной математике - https://www.amazon.com/gp/product/0130458031/ref=as_li_tl?ie=UTF8&tag=everythingc06-20&camp=1789&creative=9325&linkCode=as2&creativeASIN=0130458031&linkId=5ec571a3f11c8356c4a977dd95945e21 (2) Рабочая тетрадь по дискретной математике - https://www.amazon.com/gp/product/0130463272/ref=as_li_tl?ie=UTF8&tag=everythingc06-20&camp=1789&creative=9325&linkCode=as2&creativeASIN=0130463272&linkId=722a147e4912843adb18019b7a08a7e4