В примерах ранее мы использовали только простые операции — присваивание, сравнение, арифметику. Однако, программы часто работают с библиотечными классами, вызывая у них разные методы. В таких ситуациях важно понимать сложность всех этих методов. Давайте поупражняемся на примере строк.

Класс строки string в .NET внутри представляет собой непрерывную область памяти, где хранятся символы строки и длина всей строки. Он неизменяемый. Это значит, что любая операция по модификации строки не меняет саму строку, а создает новую, являющуюся результатом модификации. Естественно, для создания новой строки, нужно выделить под неё новый непрерывный участок памяти и скопировать туда все её символы.

Используя эти знания о строках в .NET, постарайтесь догадаться о сложности основных методов класса string.

Пусть есть строка s длины n символов.

1. Какая сложность у операции s[i] — получения i-ого символа в строке? 1 балл

2. Какая сложность у операции s.Length — получения длины строки? 1 балл

3. Какая сложность у операции s.Substring(startIndex, count) — получения подстроки длины count, начиная с startindex? 1 балл

4. Какая сложность у операции s.IndexOf("a") — поиска первого вхождения символа 'a' в строке s? 1 балл

5. Какая сложность у операции s.Replace("abc", "def") — замены всех вхождений строки "abc" в строке s на строку "def"? 1 балл

6. Какая сложность у операции s.Replace("a", v) — замены всех вхождений строки "a" в строке s на строку v (длиной не более n)? 1 балл