def check_palin(word):
for i in range(len(word)//2):
if word[i] != word[-(i+1)]:
return False
return True
I guess this is a bit more efficient solution as it iterates over half of the string and returns False whenever the condition is violated. But still the complexity would be O(n)
I'm getting ready for an interview and practicing time complexity and I'm ok at recognizing the complexity for the code I've written myself but have a harder time when I throw in methods from the java library.
For example, I read that the method concat was similar to += and that concat time complexity was O(n^2). So if I reverse a string with the code below does that mean my time complexity is O(n^2)? With a space complexity of O(n) since? Where n is the length of the string.
String str="hello"
String s="";
for(int i =str.length()-1; i>=0;i--){
s+=str.substring(i,i+1);
}With this code is the space complexity O(n) and the time complexity O(n)? Where n is the length of the string.
String str="hello";
char[] cArr = str.toCharArray();
int i =0;
int j = cArr.length-1;
char temp;
while(i<j){
temp =cArr[i];
cArr[i]=cArr[j];
cArr[j]=temp;
i++;
j--;
}
str=String.valueOf(cArr);performance - String reversal in Python - Code Review Stack Exchange
python - Reverse string time and space complexity - Stack Overflow
Time complexity of reversed() in Python 3 - Stack Overflow
python - What is the time complexity of this reverse string function? - Stack Overflow
Are the Python string reversal methods similar to the ways you can reverse a string in C?
How does string slicing work in Python?
What are the ways to reverse a string in Python using inbuilt function?
Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Even worse is doing so in a loop, because this has to happen ever time. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).
But here you can just use the fact that strings can be sliced and you can specify a negative step:
def reverse_g(s):
return s[::-1]
Here is a timing comparison for random strings of length from one up to 1M characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is almost a hundred thousand times slower.
The reverse_s function uses the reversed built-in, as suggested in the (now deleted, so 10k+ reputation) answer by @sleblanc and assumes you actually need the reversed string and not just an iterator over it:
def reverse_s(s):
return ''.join(reversed(s))
The reverse_b function uses the C implementation, compiled with -O3, provided in the answer by @Broman, with a wrapper to create the string buffers and extract the output:
from ctypes import *
revlib = cdll.LoadLibrary("rev.so")
_reverse_b = revlib.reverse
_reverse_b.argtypes = [c_char_p, c_char_p, c_size_t]
def reverse_b(s):
stri = create_string_buffer(s.encode('utf-8'))
stro = create_string_buffer(b'\000' * (len(s)+1))
_reverse_b(stro, stri, len(s) - 1)
return stro.value.decode()
In the no interface version, just the call to _reverse_b is timed.
In terms of pure complexity, the answer is simple: No, it is not possible to reverse a string faster than O(n). That is the theoretical limit when you look at the pure algorithm.
However, your code does not achieve that because the operations in the loop are not O(1). For instance, output += stri[-1] does not do what you think it does. Python is a very high level language that does a lot of strange things under the hood compared to languages such as C. Strings are immutable in Python, which means that each time this line is executed, a completely new string is created.
If you really need the speed, you could consider writing a C function and call it from Python. Here is an example:
rev.c:
#include <stddef.h>
void reverse(char * stro, char * stri, size_t length) {
for(size_t i=0; i<length; i++) stro[i]=stri[length-1-i];
stro[length]='\0';
}
Compile the above function with this command:
gcc -o rev.so -shared -fPIC rev.c
And here is a python script using that function.
rev.py:
from ctypes import *
revlib = cdll.LoadLibrary("rev.so");
reverse = revlib.reverse
reverse.argtypes = [c_char_p, c_char_p, c_size_t]
hello = "HelloWorld"
stri = create_string_buffer(hello)
stro = create_string_buffer(b'\000' * (len(hello)+1))
reverse(stro, stri, len(stri)-1)
print(repr(stri.value))
print(repr(stro.value))
Please note that I'm by no means an expert on this. I tested this with string of length 10⁸, and I tried the method from Graipher, calling the C function from Python and calling the C function from C. I used -O3 optimization. When I did not use any optimization it was slower to call the C function from Python. Also note that I did NOT include the time it took to create the buffers.
stri[::-1] : 0.98s
calling reverse from python : 0.59s
calling reverse from c: 0.06s
It's not a huge improvement, but it is an improvement. But the pure C program was WAY faster. The main function I used was this one:
int __attribute__((optimize("0"))) // Disable optimization for main
main(int argc, char ** argv) { // so that reverse is not inlined
const size_t size = 1e9;
char * str = malloc(size+1);
static const char alphanum[] =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// Take data from outside the program to fool the optimizer
alphanum[atoi(argv[1])]='7';
// Load string with random data to fool the optimizer
srand(time(NULL));
for (size_t i = 0; i < size; ++i) {
str[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
}
char *o = malloc(size+1);
reverse(o, str, strlen(str));
// Do something with the data to fool the optimizer
for(size_t i=0; i<size; i++)
if(str[i] != o[size-i-1]) {
printf("Error\n");
exit(1);
}
}
Then, to get the runtime I ran:
gcc -O3 -pg rev.c; ./a.out; gprof a.out gmon.out | head -n8
Let T(n) represent the time complexity for the recReverseString function. Then we have the following equation
// Assuming len(s) is O(1) but slicing would be O(n)
T(n) = 2T(n/2) + O(n)
The solution for this equation is O(nlogn).
Take binary search as an example for a divide and conquer algorithm. In binary search the recursive call takes one half of the array. Hence the recursive equation in that case is
T(n) = T(n/2) + 1
The solution for this equation is O(logn)
We may as well assume that the length of the initial sequence is to the nth power of 2. Considering that len is O(1) and both twice slicing and connect two lists are O(n), we can list such an equation:
T(n) = 2T(n/2) + O(n) (1)
Replace n with n/2, we can get:
T(n/2) = 2T(n/4) + O(n/2) (2)
After logn times of replacement, we can get:
T(2) = 2T(1) + O(1) (3)
Substituting equation 2 into equation 1, we have:
T(n) = 4T(n/4) + 2O(n/2) + O(n) = 4T(n/4) + 2O(n)
Substituting logn times repeatedly until equation 3, and the following can be obtained:
T(n) = nT(1) + logn * O(n) = O(n) + O(nlogn) = O(nlogn)
So the time complexity of your method is O(nlogn).